중위 표현식을 후위 표현식으로 변환

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"
#include <stdio.h>
#include <ctype.h>

#define EXPMAX 256

int getPriorty(char op) {
	switch (op) {
	default: // (, ), ...
		return 0;
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
		return 2;
	}
}

int main()
{
	int pos = 0;
	char postExp[EXPMAX];

	char preExp[EXPMAX] = { 0, };
	printf("중위 표기식: ");
	scanf("%s", preExp);

	ArrayStack* opStack = NULL;
	AS_CreateStack(&opStack, EXPMAX);

	for (int i = 0; i < EXPMAX; i++) {
		if (isdigit(preExp[i])) {
			postExp[pos++] = preExp[i];
		}
		else {
			char op = preExp[i];
			if (op == '(') {
				AS_Push(opStack, op);
				continue;
			}
			else if (op == ')') {
				while (!AS_IsEmpty(opStack) && AS_Top(opStack) != '(') {
					postExp[pos++] = AS_Pop(opStack);
				}
				AS_Pop(opStack);
				continue;
			}
			else if (!AS_IsEmpty(opStack)) {
				while (!AS_IsEmpty(opStack) && getPriorty(AS_Top(opStack)) >= getPriorty(op)) {
					postExp[pos++] = AS_Pop(opStack);
				}
			}
			AS_Push(opStack, op);
		}
	}
	while (!AS_IsEmpty(opStack)) {
		postExp[pos++] = AS_Pop(opStack);
	}
	AS_DestroyStack(opStack);
	printf("후위 표기식: %s\n", postExp);

	system("pause");
	return 0;
}

후위 연산자로 변환

중위 표기식의 문자를 왼쪽에서 오른쪽으로 읽는다.

숫자는 무조건 후위 표기식에 추가한다.

여는 괄호는 무조건 연산자 스택에 추가한다.

닫는 괄호를 만나면 여는 괄호 전 까지의 모든 연산자를 연산자 스택에서 꺼내 후위 표기식에 추가하고 여는 괄호를 꺼내 버린다.

연산자는 (연산자 스택의 Top에 담긴 연산자의 우선순위와 같거나 높을 경우에) 의 조건을 만족하지 않을 때 까지 꺼내 후위 표기식에 추가한다.