c++: 후위 표현식 구현하기

컴퓨터에서 괄호가 포함된 연산을 쉽게 처리하기 위해서는, 중위 표현식(Infix)보다 후위 표현식(Postfix)을 통해 계산하면 쉽게 처리할 수 있다. 이는 Stack을 통해 쉽게 구현할 수 있으며, 변환한 식을 계산하는 것은 어렵지 않다.

Stack을 사용하여 구현

후위 표현식 변환

int priority(char c)
{
    if (c == '(')
        return 0;
    else if (c == '+' || c == '-')
        return 1;
    // *, / 인 경우
    return 2;
}

string changePostfix(string target)
{
    stack<char> s;
    string prefix;

    for (int i = 0; target[i]; i++) {
        if (target[i] == '(')
            s.push('(');
        else if (target[i] == ')') {
            while (s.top() != '(') {
                prefix += s.top();
                s.pop();
            }
            s.pop();
        }
        else if (target[i] == '+' || target[i] == '/' || target[i] == '*' || target[i] == '-') {
            while (!s.empty() && priority(target[i]) <= priority(s.top())) {
                prefix += s.top();
                s.pop();
            }
            s.push(target[i]);
        }
        else { // 피연산자.
            prefix += target[i];
        }
    }

    while (!s.empty()) {
        prefix += s.top();
        s.pop();
    }

    return prefix;
}

 후위 표현식을 스택을 사용하여 변환할 때 조건은 다음과 같다.

• `피연산자`인 경우 바로 출력한다.
• 연산자가 들어오면 `우선순위가 높거나 같은 것은 제외`하고 스택에 push 한다.
• `여는 괄호'('`가 들어온 이후로는 무조건 스택에 push 한다.
• `닫는 괄호')'`가 들어오면 `'('`일 때까지 스택에서 pop 한다.

 

후위 표현식 계산

int vars[26];

int calcPostfix(string target) {
    stack<int> s;

    for (int i = 0; target[i]; i++) {
        if (isdigit(target[i]) || isalpha(target[i])) {
            int curNum = !isalpha(target[i]) ? target[i] - '0' : vars[target[i] - 'A'];
            s.push(curNum);
        }
        else {
            int op2 = s.top();
            s.pop();

            int op1 = s.top();
            s.pop();

            switch (target[i]) {
            case '+': s.push(op1 + op2); break;
            case '-': s.push(op1 - op2); break;
            case '*': s.push(op1 * op2); break;
            case '/': s.push(op1 / op2); break;
            }
        }
    }

    return s.top();
}

 후위 표현식을 계산하는 데 있어, 연산자 말고 식에서 `A, B, C`와 같은 변수들과 일반적인 숫자가 있는 경우에도 계산할 수 있도록 하였다. 우선 값을 계산하기 위해서 중요한 것은 stack을 int형으로 선언하여야 한다는 것이다. 또한 `cctype`에 선언된 `isdigit`, `isalpha`, `isalpha`를 사용하여서 변수인지, 숫자인지 구분하여서 처리하면 된다.

 vars는 A ~ Z까지의 변수들의 값을 저장하기 위한 변수이다. 이에 대한 인덱스 접근은 `vars[문자 - 'A']`와 같이 접근하면 된다. 숫자의 경우 int형으로 변환하고자 할 때, `문자 - '0'`을 통해 변환할 수 있다.

 

// 숫자인 경우.
if ('0' <= target[i] && target[i] <= '9) {
    // Do something.
}
// A ~ Z인 경우
else if ('A' <= target[i] && target[i] <= 'Z') {
    // Do something
} 
// 연산자인 경우
else {
    // Do something
}

 별도의 `include` 없이, string을 index 별로 접근하게 되면 char이므로, 위와 같이 숫자, 문자, 연산자 구분도 가능하다.

 

 변환한 후위 표현식을 계산하는 과정은 간단하다.

• `피연산자`인 경우 stack에 push 한다.
• `연산자`인 경우 stack에서 2개의 수를 pop 하여 계산한다.
  • 계산된 값을 stack에 push 한다.
• 마지막에 stack에 남는 값이 최종 계산 값이다.

 

전체 코드

#include <stack>
#include <string>
#include <cctype>
#include <sstream>
#include <iostream>

using namespace std;

int vars[26];

int priority(char c)
{
    if (c == '(')
        return 0;
    else if (c == '+' || c == '-')
        return 1;
    // *, / 인 경우
    return 2;
}

string changePostfix(string target)
{
    stack<char> s;
    string prefix;

    for (int i = 0; target[i]; i++) {
        if (target[i] == '(')
            s.push('(');
        else if (target[i] == ')') {
            while (s.top() != '(') {
                prefix += s.top();
                s.pop();
            }
            s.pop();
        }
        else if (target[i] == '+' || target[i] == '/' || target[i] == '*' || target[i] == '-') {
            while (!s.empty() && priority(target[i]) <= priority(s.top())) {
                prefix += s.top();
                s.pop();
            }
            s.push(target[i]);
        }
        else { // 피연산자.
            prefix += target[i];
        }
    }

    while (!s.empty()) {
        prefix += s.top();
        s.pop();
    }

    return prefix;
}

int calcPostfix(string target) {
    stack<int> s;

    for (int i = 0; target[i]; i++) {
        if (isdigit(target[i]) || isalpha(target[i])) {
            int curNum = !isalpha(target[i]) ? target[i] - '0' : vars[target[i] - 'A'];
            s.push(curNum);
        }
        else {
            int op2 = s.top();
            s.pop();

            int op1 = s.top();
            s.pop();

            switch (target[i]) {
            case '+': s.push(op1 + op2); break;
            case '-': s.push(op1 - op2); break;
            case '*': s.push(op1 * op2); break;
            case '/': s.push(op1 / op2); break;
            }
        }
    }

    return s.top();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string test = "5+A*(B+C)";

    vars[0] = 7; // A = 7
    vars[1] = 10; // B = 10
    vars[2] = 15; // C = 15

    string post = changePostfix(test);
    cout << post << endl;
    cout << calcPostfix(post) << endl;
}

 

망각 속도는 생각보다 빠르다..

• 2020.06.24 - [👨‍💻 코딩테스트/백준] - 백준: 1918 후위 표기식
• 2020.06.24 - [👨‍💻 코딩테스트/백준] - 백준: 1935 후위 표기식2

 약, 2년 전쯤에 문제 풀이를 위해 공부를 했다... 망각 속도가 빨라서 잊어버리고 다시 공부하게 되는 것을 반복하고 있다.