4.2.2) 표기법 변환을 위한 스택의 활용
식을 중위 표기법에서 후위 표기법으로 변환하는 과정은 다음과 같이 진행된다.
1. 피연산자라면 ‘후위 표기식’의 끝에 추가한다.
2. 연산자라면? -> ‘연산자 보관소’의 상태를 확인한다.
2.1) ‘연산자 보관소’에 저장된 연산자가 없다면 추가한다.
2.2) ‘연산자 보관소’에 저장된 연산자가 있다면? -> 연산자의 우선순위를 비교한다.
2.2.1) 보관소에 마지막으로 저장된 연산자가 우선순위가 높다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 보관소에서 꺼내 ‘후위 표기식’의 끝에 추가하고 새 연산자를 보관소에 저장한다.
2.2.2) 새 연산자의 우선순위가 높다면 새 연산자를 보관소에 저장한다.
2.2.3) 두 연산자의 우선순위가 같다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 보관소에서 꺼내‘후위 표기식’의 끝에 추가하고 새 연산자를 보관소에 저장한다.
3. 1~2 과정을 반복한다.
4. 분석이 끝나면 보관소에 남은 모든 연산자를 ‘후위 표기식’에 추가한 후 ‘후위 표기식’을 반환하고 종료한다.
이를 위해 스택을 활용할 수 있다.
1. 피연산자라면 ‘후위 표기식’ 배열의 끝에 추가한다.
2. 연산자라면? -> ‘연산자 스택’의 상태를 확인한다.
2.2.1) 스택의 최상위 연산자가 우선순위가 높다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 스택에서 팝 하여 ‘후위 표기식’의 끝에 추가하고 새 연산자를 스택에 푸시 한다.
2.2.2) 새 연산자의 우선순위가 높다면 새 연산자를 보관소에 푸시 한다.
2.2.3) 두 연산자의 우선순위가 같다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 스택에서 팝 하여‘후위 표기식’의 끝에 추가하고 새 연산자를 스택에 푸시 한다.
3. 1~2 과정을 반복한다.
4. 분석이 끝나면 스택에 남은 모든 연산자를 ‘후위 표기식’에 추가한 후 ‘후위 표기식’을 반환하고 종료한다.
다음은 스택을 활용하여 중위 표기식을 후위 표기식으로 변환하는 예제이다. 소괄호에 대한 처리는 아직 설명하지 않았으므로 적용하지 않았다.
|
03_in_to_post.cpp |
|
#include <iostream> typedef std::string Exception; // 공용 함수 inline bool is_digit(char ch) { return ('0' <= ch && ch <= '9'); } // 스택 정의 typedef char Data; class Stack { static const int MAX_STACK_SIZ = 256; Data _list[MAX_STACK_SIZ]; int _count; private: inline bool is_full() const { return _count == MAX_STACK_SIZ; } public: Stack() : _count(0) {} void push(const Data &data) { if (is_full()) throw Exception("Stack is full"); _list[_count++] = data; } Data pop() { if (is_empty()) throw Exception("Stack is empty"); return _list[--_count]; } Data top() const { if (is_empty()) throw Exception("Stack is empty"); return _list[_count - 1]; } inline bool is_empty() const { return _count == 0; } inline int count() const { return _count; } }; // 사용할 함수 int op_pri(char ch); // get operator's priority // convert infix notation expression // to postfix notation expression void infix_to_postfix(char *postfix, const char *infix); int main(void) { try { int loop; std::cin >> loop; const int MAX_EXPR_LEN = 256; char infix[MAX_EXPR_LEN] = ""; char postfix[MAX_EXPR_LEN] = ""; while (loop-- > 0) { std::cout << "Enter expression: "; std::cin >> infix; infix_to_postfix(postfix, infix); std::cout << infix << " : " << postfix << std::endl; } return 0; } catch (Exception &ex) { std::cerr << ex.c_str() << std::endl; return 1; } } // 구현 int op_pri(char ch) { // get operator's priority int priority = 0; switch (ch) { case '+': priority = 1; break; case '-': priority = 1; break; case '*': priority = 2; break; case '/': priority = 2; break; default: throw Exception("Invalid operator"); } return priority; } void infix_to_postfix(char *postfix, const char *infix) { // convert infix notation expression // to postfix notation expression if (is_digit(*infix) == false) throw Exception("Invalid infix notation expression"); char ch; Stack opStack; // operator stack for (ch = *infix; (ch = *infix) != '\0'; ++infix) { if (is_digit(ch)) { while (is_digit(*infix)) { *postfix++ = *infix++; } --infix; } else { // is_operator if (opStack.is_empty() == false) { // get operator priority int new_pri = op_pri(ch); while (opStack.is_empty() == false) { if (new_pri <= op_pri(opStack.top())) { *postfix++ = opStack.pop(); } else { break; } } } opStack.push(ch); } } // 스택에 남은 연산자를 while (opStack.is_empty() == false) { char op = opStack.pop(); *postfix++ = op; } *postfix = '\0'; } |
