문제 풀이/백준
BOJ 1918번: 후위 표기식
danbibibi
2023. 3. 7. 16:43
문제
문제 바로가기> BOJ 1918번: 후위 표기식
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
풀이
#include<iostream>
#include<string>
#include<stack>
#define MAX 32001
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
string expr; cin >> expr;
stack<char> st; // 우선 순위가 낮은 연산자 (+, -) 부터 큰 연산자 (*, /) 순으로 쌓임
// 연산자 우선 순위 : () > *, / > +, -
for (int i = 0; i < expr.size(); i++) {
if (expr[i] == '+' || expr[i] == '-') {
while (!st.empty() && st.top()!='(') {
cout << st.top(); st.pop();
}
st.push(expr[i]);
}
else if (expr[i] == '*' || expr[i] == '/') {
while (!st.empty() && (st.top() == '*' || st.top() == '/')) {
cout << st.top(); st.pop();
}
st.push(expr[i]);
}
else if (expr[i] == '(') st.push(expr[i]);
else if (expr[i] == ')') {
while (st.top() != '(') {
cout << st.top();
st.pop();
} st.pop(); // '(' pop
}
else cout << expr[i]; // 알파벳 대문자
}
while (!st.empty()) { // 남은 연산자 출력
cout << st.top(); st.pop();
}
}