이 글에서는 접두사 표현식(prefix expression)을 평가하는 방법에 대해 자세히 알아보겠습니다.
접두사 표현식이란?
접두사 표기법에서는 연산자가 피연산자 앞에 위치합니다. 즉, 연산자를 피연산자보다 먼저 작성하는 방식입니다. 예를 들어 +ab는 중위 표기법(infix notation)의 a + b와 동일한 의미를 가집니다. 접두사 표기법은 폴란드 표기법(Polish Notation)이라고도 불립니다.
예시
* + 6 9 - 3 1
접두사 표현식은 중위 표현식보다 더 빠르게 평가할 수 있다는 장점이 있습니다. 또한 접두사 표현식에는 괄호가 없기 때문에 연산 우선순위를 고려할 필요가 없어 계산이 더욱 간단하고 빠릅니다.
접두사 표현식 평가 알고리즘
접두사 표현식을 평가하려면 스택(stack) 자료구조가 필요합니다. 표현식의 각 요소를 스택에 넣고(push) 빼면서(pop) 연산을 수행하는 방식으로 진행됩니다.
표현식의 각 요소를 하나씩 방문하며, 현재 요소가 피연산자라면 스택에 push합니다. 반면 현재 요소가 연산자라면 스택에서 피연산자 두 개를 pop하여 연산을 수행한 뒤(피연산자 연산자 피연산자 순서로 계산), 그 결과를 다시 스택에 push합니다.
알고리즘 단계
1단계: 표현식의 마지막 요소부터 시작합니다.
2단계: 현재 요소를 확인합니다.
2.1단계: 피연산자라면 스택에 push합니다.
2.2단계: 연산자라면 스택에서 피연산자 두 개를 pop합니다. 연산을 수행한 후 결과를 다시 스택에 push합니다.
3단계: 표현식의 모든 요소를 순회할 때까지 위 과정을 반복한 뒤, 스택의 top 값을 반환합니다. 이 값이 최종 연산 결과입니다.
알고리즘 동작 과정 살펴보기
접두사 표현식: * + 6 9 - 3 1
반복 1
스캔한 요소 => 1
연산 => 스택에 push
스택 => 1
반복 2
스캔한 요소 => 3
연산 => 스택에 push
스택 => 3, 1
반복 3
스캔한 요소 => -
연산 => 스택에서 두 개를 pop하여 연산 수행 후 결과를 다시 push
3 - 1 = 2
스택 => 2
반복 4
스캔한 요소 => 9
연산 => 스택에 push
스택 => 9, 2
반복 5
스캔한 요소 => 6
연산 => 스택에 push
스택 => 6, 9, 2
반복 6
스캔한 요소 => +
연산 => 스택에서 두 개를 pop하여 연산 수행 후 결과를 다시 push
6 + 9 = 15
스택 => 15, 2
반복 7
스캔한 요소 => *
연산 => 스택에서 두 개를 pop하여 연산 수행 후 결과를 다시 push
15 * 2 = 30
스택 => 30
종료 => 스택의 top 값을 반환, 결과 = 30
솔루션 구현 예제 코드
아래는 위 알고리즘을 C++로 구현한 예제 코드입니다.
#include <bits/stdc++.h>
using namespace std;
double evaluatePrefix(string prefixExp) {
stack<double> operendStack;
int size = prefixExp.size() - 1;
for (int i = size; i >= 0; i--) {
if (isdigit(prefixExp[i]))
operendStack.push(prefixExp[i] - '0');
else {
double o1 = operendStack.top();
operendStack.pop();
double o2 = operendStack.top();
operendStack.pop();
if( prefixExp[i] == '+')
operendStack.push(o1 + o2);
else if( prefixExp[i] == '-')
operendStack.push(o1 - o2);
else if( prefixExp[i] == '*')
operendStack.push(o1 * o2);
else if( prefixExp[i] == '/')
operendStack.push(o1 / o2);
else{
cout<<"Invalid Expression";
return -1;
}
}
}
return operendStack.top();
}
int main()
{
string prefixExp = "*+69-31";
cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
return 0;
}
실행 결과
The result of evaluation of expression *+69-31 is 30
위 코드는 표현식을 뒤에서부터 한 글자씩 스캔하며, 숫자라면 스택에 push하고 연산자라면 두 개의 피연산자를 꺼내 연산한 결과를 다시 스택에 넣는 방식으로 동작합니다. 모든 문자를 처리한 후 스택에 남아 있는 값이 곧 접두사 표현식의 최종 결과가 됩니다.