PS/BOJ
[C++] 백준 1918번: 후위 표기식 - Stack
__PS
2023. 3. 13. 20:05
728x90
https://www.acmicpc.net/problem/1918
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
처음에는 상당히 애를 먹었던 문제
처음에 접근했던 방식은
(+) 연산자나 (-) 연산자는 (*) 연산자와 (/) 연산자보다 우선순위가 밀리기때문에 바로바로 출력하지 않고
뒤에 나오는 연산자를 기다리다가 출력을 하는 형식으로,
(*)연산자와 (/)연산자는 우선순위는 높지만 뒤에 또 (*)연산자나 (/)연산자가 나오게 된다면 연속적으로 이루어지기에
역시 저장을 한 후 출력을 하는 형식으로,
괄호가 포함되면 괄호가 나오기 전까지 어쩌구저쩌구..
상당히 복잡하게 생각했었는데,
가만 생각해보니 그냥 전부 저장을 한 후 괄호가 나오기 전까지 출력을 해주면 되는 문제였다..
단지 (+)연산자나 (-)연산자가 나왔을 때는 무지성 저장을,
(*)연산자와 (/)연산자가 나왔을 경우 저장된 기호가 (*)연산자와 (/)연산자가 나올 때까지 출력을 해주면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#include <stack>
using namespace std;
int main(){
string s; cin >> s;
stack<char>st;
for(int i=0; i<s.length(); i++){
if(s[i]>='A' && s[i]<='Z') cout << s[i];
else if(s[i]=='(') st.push(s[i]);
else if(s[i]==')'){
while(!st.empty() && st.top()!='('){
cout << st.top();
st.pop();
}
if(!st.empty() && st.top()=='(') st.pop();
}
else if(s[i]=='+' || s[i]=='-'){
while(!st.empty() && st.top()!='('){
cout << st.top();
st.pop();
}
st.push(s[i]);
}
else if(s[i]=='*' || s[i]=='/'){
while(!st.empty() && st.top()!='(' && st.top()!='+' && st.top()!='-') {
cout << st.top();
st.pop();
}
st.push(s[i]);
}
}
while(!st.empty()){
cout << st.top();
st.pop();
}
}
|
cs |