[백준] 후위 표기식 #1918

설명

아직 골드 정도의 난이도는 스스로 풀이를 떠올리는데에 힘이 드는 것 같다.
다른 사람의 풀이를 참고했고 이 문제는 스택 자료구조를 사용해서 풀 수 있다.
주어진 문자열을 앞에서 부터 하나씩 체크하면서 answer에 결과를 더해준다.
일반 알파벳일 경우 그냥 더해주고, 다른 연산자의 경우 규칙에 맞게 스택을 활용해 담아서 처리한다.

1. (를 만나면 스택에 그냥 푸시한다.
2. *와 / 연산자의 경우 다른 연산자 보다 우선순위가 크므로 그냥 스택에 푸시해주면 되지만 이미 먼저 스택에 *와 / 연산자가 담겨있는 경우 해당 연산자의 우선 순위가 높으므로 그 연산자만 미리 꺼내어 answer에 더해준다.
3. +와 - 연산자는 연산자의 우선 순위가 낮으므로 스택에 담겨진 모든 연산자를 꺼내어 answer에 더해준다.
4. ) 연산자의 경우 스택에 담겨있는 연산자들의 우선순위가 가장 높으므로(괄호에 둘러싸여 있어서) (가 스택의 top일 때까지 answer에 pop하여 더해준다.
   그리고 마지막으로 (를 제거해야 해서 while문 종료 후에 한 번더 pop 해준다.

위의 규칙으로 JS와 C++를 사용해서 풀었다.

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

class Stack {
  constructor() {
    this.stack = [];
  }
  push(value) {
    this.stack.push(value);
  }
  pop() {
    if (this.size() === 0) return -1;
    return this.stack.pop();
  }
  top() {
    return this.size() ? this.stack[this.size() - 1] : -1;
  }
  size() {
    return this.stack.length;
  }
  empty() {
    return this.size() === 0 ? 1 : 0;
  }
}

const solution = (str) => {
  const stack = new Stack();
  let answer = '';
  const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  for (const ch of str) {
    if (alphabet.includes(ch)) {
      answer += ch;
    } else if (ch === '(') {
      stack.push('(');
    } else if (ch === '*' || ch === '/') {
      while (stack.top() === '*' || stack.top() === '/') answer += stack.pop();
      stack.push(ch);
    } else if (ch === '+' || ch === '-') {
      while (!stack.empty() && stack.top() !== '(') answer += stack.pop();
      stack.push(ch);
    } else if (ch === ')') {
      while (!stack.empty() && stack.top() !== '(') answer += stack.pop();
      stack.pop();
    }
  }
  while (!stack.empty()) answer += stack.pop();
  return answer;
};

console.log(solution(input));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string str; cin >> str;
    stack<char> S;
    string answer = "";
    
    for (auto &ch : str) {
        if ('A' <= ch && ch <= 'Z') answer += ch;
        else if (ch == '(') S.push(ch);
        else if (ch == ')') {
            while(!S.empty() && S.top() != '(') {
                answer += S.top(); 
                S.pop();
            }
            S.pop();
        }
        else if (ch == '*' || ch == '/') {
            while(!S.empty() && (S.top() == '*' || S.top() == '/')) {
                answer += S.top(); 
                S.pop();
            }
            S.push(ch);
        }
        else if (ch == '+' || ch == '-') {
            while(!S.empty() && S.top() != '(') {
                answer += S.top();
                S.pop();
            }
            S.push(ch);
        }
    }
    while(!S.empty()) {
        answer += S.top(); 
        S.pop();
    }
    cout << answer << '\n';
    return 0;
}