개요
컴퓨터는 사람이 일반적으로 사용하는 중위(infix) 표기식을 그대로 계산하기 어렵습니다. 따라서 연산자 우선순위를 명확하게 반영할 수 있도록 후위(postfix) 또는 전위(prefix) 표기식으로 변환한 뒤 계산을 수행합니다. 이 글에서는 중위 표기식을 전위 표기식으로 변환하는 방법을 단계별로 살펴보겠습니다.
변환 절차
중위 표기식을 전위 표기식으로 바꾸는 과정은 다음 네 단계로 진행됩니다.
- 중위 표기식을 뒤집습니다. 이때 여는 괄호 '(' 와 닫는 괄호 ')' 도 함께 뒤집힌다는 점에 유의해야 합니다.
- 괄호 방향을 교환합니다. 뒤집힌 식에서 여는 괄호는 닫는 괄호로, 닫는 괄호는 여는 괄호로 서로 바꾸어 줍니다.
- 중위 → 후위 변환 알고리즘을 적용합니다. 변형된 중위 표기식을 기존의 중위-후위 변환 알고리즘을 이용해 후위 표기식으로 만듭니다.
- 결과를 다시 뒤집습니다. 얻어진 후위 표기식을 한 번 더 역순으로 뒤집으면 최종적인 전위 표기식이 완성됩니다.
예를 들어 수식 A + B * (C - D)를 단순히 뒤집으면 ) D – C ( * B + A가 됩니다. 이 상태에서는 괄호의 짝이 맞지 않으므로, 여는 괄호와 닫는 괄호를 서로 교환한 뒤 후위 변환과 재역순 과정을 거쳐야 올바른 전위 표기식을 얻을 수 있습니다.
입력 및 출력
입력:
중위 표기식: x^y/(5*z)+2
출력:
전위 표기식: +/^xy*5z2
알고리즘
infixToPrefix(infix)
입력 − 전위 표기식으로 변환할 중위 표기식
출력 − 변환된 전위 표기식
시작
중위 표기식을 뒤집는다
뒤집힌 중위 표기식의 각 문자 ch에 대해 반복:
ch가 여는 괄호이면 닫는 괄호로 변경
그렇지 않고 ch가 닫는 괄호이면 여는 괄호로 변경
반복 종료
postfix := 변형된 중위 표기식을 후위 표기식으로 변환
prefix := 최근에 계산한 후위 표기식을 다시 뒤집음
prefix 반환
종료
C++ 구현 예제
#include<iostream>
#include<stack>
#include<locale> //isalnum() 함수 사용을 위한 헤더
#include<algorithm>
using namespace std;
int preced(char ch) {
if(ch == '+' || ch == '-') {
return 1; // + 또는 - 의 우선순위는 1
}else if(ch == '*' || ch == '/') {
return 2; // * 또는 / 의 우선순위는 2
}else if(ch == '^') {
return 3; // ^ 의 우선순위는 3
}else {
return 0;
}
}
string inToPost(string infix) {
stack<char> stk;
stk.push('#'); // 스택 언더플로우 방지를 위한 임시 문자 추가
string postfix = ""; // 초기 후위 표기식은 빈 문자열
string::iterator it;
for(it = infix.begin(); it!=infix.end(); it++) {
if(isalnum(char(*it)))
postfix += *it; // 문자나 숫자인 경우 후위 표기식에 추가
else if(*it == '(')
stk.push('(');
else if(*it == '^')
stk.push('^');
else if(*it == ')') {
while(stk.top() != '#' && stk.top() != '(') {
postfix += stk.top(); // '(' 를 만날 때까지 저장 후 pop
stk.pop();
}
stk.pop(); // 스택에서 '(' 제거
}else {
if(preced(*it) > preced(stk.top()))
stk.push(*it); // 우선순위가 높으면 push
else {
while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
postfix += stk.top(); // 더 높은 우선순위를 만날 때까지 저장 후 pop
stk.pop();
}
stk.push(*it);
}
}
}
while(stk.top() != '#') {
postfix += stk.top(); // 스택이 빌 때까지 저장 후 pop
stk.pop();
}
return postfix;
}
string inToPre(string infix) {
string prefix;
reverse(infix.begin(), infix.end()); // 중위 표기식을 뒤집음
string::iterator it;
for(it = infix.begin(); it != infix.end(); it++) { // 뒤집은 후 괄호 방향을 다시 교정
if(*it == '(')
*it = ')';
else if(*it == ')')
*it = '(';
}
prefix = inToPost(infix); // 변형된 중위 표기식을 후위 표기식으로 변환
reverse(prefix.begin(), prefix.end()); // 결과를 다시 뒤집어 최종 전위 표기식 생성
return prefix;
}
int main() {
string infix = "x^y/(5*z)+2";
cout << "Prefix Form Is: " << inToPre(infix) << endl;
}
실행 결과
Prefix Form Is: +/^xy*5z2
시간 복잡도
이 알고리즘은 입력 수식의 각 문자를 상수 시간 안에 처리하며, 뒤집기 연산 역시 선형 시간에 수행되므로 전체 시간 복잡도는 O(n)입니다. 여기서 n은 입력 수식의 길이입니다.