후위 표기법(Postfix Notation)으로 작성된 수식이 주어졌을 때, 그 값을 계산하는 프로그램을 만들어 보겠습니다. 후위 표기법은 역폴란드 표기법(Reverse Polish Notation)이라고도 불리며, 연산자가 피연산자 뒤에 위치하는 것이 특징입니다. 이러한 수식은 스택(Stack) 자료구조를 활용하면 효율적으로 계산할 수 있습니다.
예를 들어 수식이 "21+3*"라고 주어지면, 계산 결과는 9가 됩니다. ((2+1)×3 = 9)
평가 알고리즘 단계
- 후위 표기식의 각 문자
ch에 대해 다음을 반복 수행합니다.ch가 연산자(⊙)인 경우a:= 스택에서 첫 번째 요소를 popb:= 스택에서 두 번째 요소를 popres:= b ⊙ a 로 계산res를 스택에 push
ch가 피연산자인 경우ch를 스택에 push
- 모든 문자 처리가 끝나면 스택 최상단(top)의 값을 반환합니다.
아래 예제 코드를 통해 구체적인 동작 방식을 살펴보겠습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
float scanNum(char ch){
int value;
value = ch;
return float(value-'0');//문자를 실수형 숫자로 변환하여 반환
}
int isOperator(char ch){
if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
return 1;//연산자인 경우
return -1;//연산자가 아닌 경우
}
int isOperand(char ch){
if(ch >= '0' && ch <= '9')
return 1;//피연산자인 경우
return -1;//피연산자가 아닌 경우
}
float operation(int a, int b, char op){
//실제 연산 수행
if(op == '+')
return b+a;
else if(op == '-')
return b-a;
else if(op == '*')
return b*a;
else if(op == '/')
return b/a;
else if(op == '^')
return pow(b,a); //b^a 거듭제곱 계산
else
return INT_MIN; //음의 무한대 반환
}
float postfixEval(string postfix){
int a, b;
stack<float> stk;
string::iterator it;
for(it=postfix.begin(); it!=postfix.end(); it++){
//각 문자를 읽으며 후위 표기식 평가 수행
if(isOperator(*it) != -1){
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
stk.push(operation(a, b, *it));
}else if(isOperand(*it) > 0){
stk.push(scanNum(*it));
}
}
return stk.top();
}
main(){
string post = "21+3*";
cout <<postfixEval(post);
}입력
"21+3*"
출력
9
코드 설명
scanNum(): 문자 형태의 숫자를 실제 실수 값으로 변환합니다.isOperator(): 해당 문자가 +, -, *, /, ^ 중 하나인지 판별합니다.isOperand(): 해당 문자가 0~9 사이의 숫자인지 확인합니다.operation(): 두 피연산자와 연산자를 받아 실제 산술 연산을 수행합니다.postfixEval(): 스택을 이용해 후위 표기식 전체를 순회하며 최종 결과를 계산합니다.
이처럼 스택 자료구조만 있으면 별도의 복잡한 파싱 과정 없이도 후위 표기법 수식을 간단하고 빠르게 평가할 수 있습니다.