스택과 계산기

후위 표기식 분석을 위한 스택의 활용

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(); // 하나 남은 피연산자를 반환한다

}

이와 같이 후위 표기식을 분석할 수 있었다중위 표기식을 후위 표기식으로 변환하는 프로그램후위 표기식을 분석하고 계산하는 프로그램을 만들었으므로남은 일은 두 프로그램을 하나로 합치는 일이다어렵지 않으므로 예제 코드는 이 문서에 싣지 않으나혹 궁금할 사람들을 위해 코드는 첨부하겠다.

댓글

댓글 본문