후위 표기법

일반적으로 (A+B)*(C+D) 와 같은 연산 표기법을 중위표기법 이라 한다.

이런 표기법은 사람은 읽기 쉽지만 컴퓨터는 해석이 난감하다는 단점을 가지고 있다.

컴퓨터가 해석하기에 최적인 표기법으로 후위표기법이 있다.

 

중위표기법을 후위표기법으로 바꾸는 알고리즘은 아래와 같다.

1. 피연산자가 나오면 출력한다.
2. 연산자가 나올경우...
         스택 최상단 연산자의 우선순위가 현재 연산자의 우선순위보다 낮아질때까지 혹은 스택이 빌때 까지                 pop 하면서 출력, 이후에 현재 연산자를 push
3.여는괄호일 경우 스택에 push
4. 닫는괄호일 경우 스택내에 첫번째 여는 괄호가 나올때 까지 stack을 pop 하면서 출력(괄호는 출력X)

위 알고리즘을 적용한 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <map>
#include <stack>
 
using namespace std;
 
int main() {
    string equation = "(1+2)*(3+4)";
    map<char, int> opPriority;
    opPriority['+'] =3, opPriority['-'] =3;
    opPriority['*'] =2, opPriority['/'] =2;
    opPriority['('] =1;
    stack<char> st;
    
    for(int index = 0; index<equation.size(); index++){
        if(equation[index] >= '0' && equation[index] <= '9'){
            // 피연산자 일경우
            cout << equation[index];
        }
        else{
            // 연산자 일경우
            if(equation[index] == ')'){
                // eke는 괄호 일 경우
                while(st.top() != '('){
                    cout << st.top();
                    st.pop();
                }
                st.pop();
            }
            else{
                // 이외의 연산자
                while(true){
                    if(st.empty() || opPriority[st.top()] < opPriority[equation[index]]){
                        st.push(equation[index]);
                        break;
                    }
                    else{
                        cout << st.top();
                        st.pop();
                    }
                }
            }
        }
    }
    
    // your code goes here
    return 0;
}

 

후위 표기법으로 바뀌고 나면 연산 알고리즘은 쉽다.

후위 표기법으로 작성된 수식을 읽어나간다.
1. 피연산자일 경우 stack에 push
2. 연산자일 경우 stack 최상단 2개의 숫자를 pop 한 후, 피연산자로 연산하고 그 결과를 다시 stack에 push
수식을 끝까지 읽으면 stack에 하나의 숫자만 남게되는데, 이 수가 연산결과이다.

 

#include <iostream>
#include <string>
#include <map>
#include <stack>
 
using namespace std;
 
int main() {
    string infix_equation = "(1+2)*(3+4)";
    map<char, int> opPriority;
    opPriority['+'] = 3, opPriority['-'] = 3;
    opPriority['*'] = 2, opPriority['/'] = 2;
    opPriority['('] = 1;
    stack<char> st;
    string postfix_equation;
 
 
    for (int index = 0; index < infix_equation.size(); index++) {
        if (infix_equation[index] >= '0' && infix_equation[index] <= '9') {
            // 피연산자 일경우
            postfix_equation.push_back(infix_equation[index]);
        }
        else {
            // 연산자 일경우
            if (infix_equation[index] == ')') {
                // eke는 괄호 일 경우
                while (st.top() != '(') {
                    postfix_equation.push_back(st.top());
                    st.pop();
                }
                st.pop();
            }
            else {
                // 이외의 연산자
                if (infix_equation[index] == '(')
                    st.push(infix_equation[index]);
                else
                    while (true) {
                        if (st.empty() || opPriority[st.top()] < opPriority[infix_equation[index]]) {
                            st.push(infix_equation[index]);
                            break;
                        }
                        else {
                            postfix_equation.push_back(st.top());
                            st.pop();
                        }
                    }
            }
        }
    }
 
    while (!st.empty()) {
        postfix_equation.push_back(st.top());
        st.pop();
    }
 
    stack<int> ist;
    ist.push(postfix_equation[0] - '0');
    ist.push(postfix_equation[1] - '0');
    for (int index = 2; index < postfix_equation.size(); index++) {
        if (postfix_equation[index] >= '0' && postfix_equation[index] <= '9') {
            int value = postfix_equation[index] - '0';
            ist.push(value);
        }
        else {
            int value[2];
            value[1] = ist.top(), ist.pop();
            value[0] = ist.top(), ist.pop();
            switch (postfix_equation[index]) {
            case '+':
                ist.push(value[0] + value[1]);
                break;
 
            case '-':
                ist.push(value[0] - value[1]);
                break;
 
            case '*':
                ist.push(value[0] * value[1]);
                break;
 
            case '/':
                if (value[1] == 0) {
                    cout << "error" << endl;
                    return 1;
                }
 
                ist.push(value[0] / value[1]);
                break;
            }
        }
    }
 
    cout << ist.top() << endl;
 
    // your code goes here
    return 0;
}

 

위 풀이법도 -를 "빼기" 연산이 아닌 "음수" 기호로써는 해석 못하는 점에서 한계를 가지지만, 매커니즘 자체를 숙지하는데에는 문제없는 코드라 생각한다.