[백준][c++] 1918번: 후위표기식

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

문제 해석

중위 표기식을 후위표기식으로 변환하여 출력하는 문제입니다. 후위 표기식변환은 스택(stack)을 이용합니다.

 

풀이

• 각 문자에 대해 다음과 같은 작업을 수행합니다
  • 문자가 문자나 숫자(즉, 피연산자)인 경우, 결과 문자열에 바로 추가합니다.
  • 문자가 여는 괄호 '('인 경우, 이를 스택에 넣습니다.
  • 문자가 닫는 괄호 ')'인 경우, 스택에서 여는 괄호 '('가 나올 때까지 문자를 pop하여 결과 문자열에 추가합니다. 만약 스택의 top이 여는 괄호가 아니라면, "Invalid Expression"을 반환합니다.
  • 문자가 연산자인 경우, 스택이 비어있지 않고 스택의 top에 있는 연산자의 우선순위가 현재 연산자의 우선순위보다 높거나 같은 동안 스택에서 문자를 pop하여 결과 문자열에 추가합니다. 그리고 현재 연산자를 스택에 넣습니다.
• 이후, 스택에 남아있는 모든 연산자를 pop하여 결과 문자열에 추가합니다.

 

코드

#include <iostream>
#include "stack"
#include "string"

using namespace std;

int precedence(char ch){
    if(ch=='+' || ch=='-')return 1;
    else if(ch=='*' || ch=='/')return 2;
    else if(ch=='^')return 3;
    else return -1;
}

string InfixToPostFix(string expression){

    string result = "";
    stack<char> stack;

    for(int i=0; i<expression.length(); i++){
        char c = expression.at(i);

        if(isalnum(c))
            result.append(1, c);

        else if(c == '(')
            stack.push(c);

        else if(c == ')'){
            while (!stack.empty() && stack.top() != '(')
                result.append(1, stack.top()), stack.pop();

            if(!stack.empty() && stack.top() != '(')
                return "ERROR";
            else
                stack.pop();
        }

        else{
            while (!stack.empty() && precedence(c) <= precedence(stack.top()))
                result.append(1, stack.top()), stack.pop();
            stack.push(c);
        }
    }

    while (!stack.empty())
        result.append(1, stack.top()), stack.pop();

    return result;
}


int main() {
    string st;
    getline(cin, st);
    cout<< InfixToPostFix(st) <<endl;
    return 0;
}