4.2.4) 후위 표기식 분석을 위한 스택의 활용
후위 표기식의 분석은 다음과 같이 진행된다.
1. 피연산자라면 저장한다.
2. 연산자라면 가장 최근에 저장한 두 피연산자와 연산자를 이용하여 연산한 후 다시 저장한다.
3. 1~2 과정을 반복한다.
4. 분석이 끝나면 유일하게 남은 피연산자 하나를 반환하고 종료한다.
이를 위해 스택을 활용할 수 있다.
1. 피연산자 스택을 만들어둔다.
2. 피연산자라면 스택에 푸시 한다.
3. 연산자라면 스택에서 두 피연산자를 팝 하여 연산한 후, 연산 결과를 다시 푸시 한다.
4. 분석이 끝나면 유일하게 스택에 남은 피연산자 하나를 팝하고 종료한다.
스택을 활용하여 후위 표기식을 분석하는 예제를 보이겠다. 이때 입력에 사이띄개 해야 함에 주의하라. 즉 다음과 같이 입력해야 결과가 제대로 나온다.
|
입력 |
출력 |
|
4 1 2 + 1 2 + 3 +1 2 3 * + 12 34 + |
1 2 + : 3 1 2 + 3 + : 6 1 2 3 * + : 7 12 34 + : 46 |
스택 클래스의 정의가 템플릿을 이용하여 변경되었음에 유의하라.
|
05_read_postfix.cpp |
|
#include <iostream> typedef std::string Exception; // 공용 함수 inline void clear_input_buffer() { // 입력받기 전에 입력 버퍼를 비운다 std::cin.clear(); std::cin.ignore(std::cin.rdbuf()->in_avail()); } inline bool is_digit(char ch) { return ('0' <= ch && ch <= '9'); } // 문자가 공백인지 확인한다 inline bool is_space(char ch) { return (ch == ' ' || ch == '\t' || ch == '\n'); } // 스택 정의 template <typename Data> // 형식에 자유로운 스택을 만들기 위해 템플릿 클래스로 변경 class Stack { /* ... */ }; // 사용할 함수 int calculate_postfix(const char *postfix); // calculate postfix expression int main(void) { try { int loop; std::cin >> loop; const int MAX_EXPR_LEN = 256; char postfix[MAX_EXPR_LEN] = ""; while (loop-- > 0) { std::cout << "Enter expression: "; clear_input_buffer(); std::cin.getline(postfix, MAX_EXPR_LEN); // 공백을 포함한 줄을 입력받는다 std::cout << postfix << " : "; std::cout << calculate_postfix(postfix) << std::endl; } return 0; } catch (Exception &ex) { std::cerr << ex.c_str() << std::endl; return 1; } }
// 구현 int calculate_postfix(const char *postfix) { char ch; int digit; Stack<int> paramStack; for (ch = *postfix; (ch = *postfix) != '\0'; ++postfix) { if (is_space(ch)) { // 공백이면 무시한다 continue; } else if (is_digit(ch)) { // 피연산자라면 스택에 푸시 한다 int value = 0; while (is_digit(*postfix)) { digit = *postfix++ - '0'; value = 10 * value + digit; } paramStack.push(value); --postfix; // 반복문 재실행시 ++postfix가 실행되므로 한 칸 되돌린다 } else { // 스택에서 두 개의 피연산자를 꺼낸다 int right = paramStack.pop(); int left = paramStack.pop(); int value = 0; // 획득한 연산자로 연산한다 switch (ch) { case '+': value = left + right; break; case '-': value = left - right; break; case '*': value = left * right; break; case '/': value = left / right; break; default: throw Exception("Invalid operator"); } // 연산 결과를 다시 스택에 넣는다 paramStack.push(value); } } if (paramStack.count() != 1) { // 스택에 남은 피연산자가 1개가 아니면 예외 throw Exception("Unhandled operand found"); } return paramStack.pop(); // 하나 남은 피연산자를 반환한다 } |
이와 같이 후위 표기식을 분석할 수 있었다. 중위 표기식을 후위 표기식으로 변환하는 프로그램, 후위 표기식을 분석하고 계산하는 프로그램을 만들었으므로, 남은 일은 두 프로그램을 하나로 합치는 일이다. 어렵지 않으므로 예제 코드는 이 문서에 싣지 않으나, 혹 궁금할 사람들을 위해 코드는 첨부하겠다.
