[백준(BOJ)] 후위 표기식(1918) C++
문제 : BOJ_1918번 후위 표기식
문제 설명
Stack
중위 표기식으로 예제가 주어지면 이것을 후위 표기식으로 바꾸는 문제입니다.
피연산자는 알파벳 대문자만 나오며, ‘-‘가 가장 앞에 나오거나, ‘*‘가 생략되는 입력은 허용하지 않습니다.
stack을 상황에 맞게 활용해서 풀어야 하는 문제입니다.
Solution
전체 문자열을 입력받고 아래와 같은 규칙으로 순회합니다.
- 피연사자는 무조건 화면에 출력한다.
- ’(‘가 나오면 stack에 push 한다.
- ’)’가 나오면 ‘(‘가 나올 때까지 stack을 비우며 출력한 뒤, 마지막 ‘(‘도 출력 없이 pop 해준다.
- 연산자가 나왔을 때 stack에 top에 자신보다 우선순위가 같거나 높은 연산자가 있으면 그 연산자를 pop 해주고 화면에 출력한다.
- 우선순위가 같거나 높은 연산자가 나오지 않고 ‘(‘나 stack이 빌 때까지 계속 pop 해주다가 만나게 되면 push 해준다.
Description
(int i = 0; str[i] != '\0'; i++)
로 전체 문자열을 순회했습니다.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
stack<char> s;
int main(void) {
char str[101];
cin >> str;
stack<char> s;
for (int i = 0; str[i] != '\0'; i++) {
char value=str[i];
if (value <= 'Z' && 'A' <= value) cout << value;
else if (value == '(') s.push(value);
else if (value == ')') {
while (s.top() != '(') {
cout << s.top();
s.pop();
}
s.pop();
}
else if (s.empty()) s.push(value);
else {
while (!s.empty()) {
if (s.top() == '(') {
s.push(value);
break;
}
else if (value == '+' || value == '-') {
cout << s.top();
s.pop();
continue;
}
else if (value == '*' || value == '/') {
if (s.top() == '*' || s.top() == '/') {
cout << s.top();
s.pop();
continue;
}
else {
s.push(value);
break;
}
}
}
if (s.empty()) s.push(value);
}
}
while (!s.empty()) {
cout << s.top();
s.pop();
}
cout << '\n';
return 0;
}
PREVIOUS[BOJ] 행운의 바퀴(2840)