[BOJ] 후위 표기식(1918)

[백준(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;
}