후위 표기식 //1918

• 문제
  
  
  //시간 제한: 2초, 메모리 제한: 128MB

• 입력
  첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, , /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

• 출력
  첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

// Created by dongwan-kim on 2022/07/26.
#include<iostream>
#include<stack>

using namespace std;

stack<char> exp;
string s;

int main() {
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            cout << s[i];
        }
        if (s[i] == '(')
            exp.push('(');
        if (s[i] == ')') {
            while (!exp.empty() && exp.top() != '(') {	//'('를 만날때까지 pop
                cout << exp.top();
                exp.pop();
            }
            exp.pop();		//'('를 pop
        }

        if (s[i] == '*' || s[i] == '/') {	//곱하기 또는 나누기일 때
            while (!exp.empty() && exp.top() != '(' && exp.top() != '+' && exp.top() != '-') {
            //담겨있던 * or /들을 pop
                cout << exp.top();
                exp.pop();
            }
            exp.push(s[i]);
        }
        if (s[i] == '+' || s[i] == '-') {	//더하기 또는 나누기일 때
            while (!exp.empty() && exp.top() != '(') {	//s.top이 괄호일 때 제외하고 전부 pop
                cout << exp.top();
                exp.pop();
            }
            exp.push(s[i]);
        }
    }

    while (!exp.empty()) {
        cout << exp.top();
        exp.pop();
    }
}

풀이

전에 자료구조 수업 때 stack을 직접 구현하며 후위 표기식 문제를 풀어봤어서 크게 어렵지 않게 해결할 수 있었다.

연산자를 우선순위에 맞추기 위해 exp스택을 선언하여 사용했고
string s를 선언하여 s에 식을 담아 주고 s의 length만큼 반복문을 시행했다.
s[i]가 대문자 영어라면 그대로 출력해 주고, 연산자라면 우리가 수학 연산할 때 우선순위 대로 짜 주었다. 제일 먼저 괄호, 곱하기&나누기, 더하기&빼기 순서로 작성하였다.

s[i]가 괄호일 때, '('라면 exp에 push해주었고 이후 뒤에 ')'가 나오면 '('가 나올때까지 연산자들을 pop해주었다.

나머지는 코드 주석에 설명해 두었다.