[백준 1918] 후위 표기식 (C#, C++) - soo:bak

문제 링크

1918번 - 후위 표기식

설명

중위 표기식이 주어지는 상황에서, 피연산자는 대문자 알파벳 A-Z이고 연산자는 +, -, *, /와 괄호로 이루어진 중위 표기식(길이 ≤ 100)이 주어질 때, 이를 후위 표기식으로 변환하는 문제입니다.

연산자 우선순위는 * / > + - 이며, 괄호가 있으면 괄호 안을 먼저 계산합니다. 예를 들어 “A+BC”는 “ABC+”로, “A(B+C)”는 “ABC+“로 변환됩니다.

접근법

연산자 스택을 이용하여 중위 표기식을 후위 표기식으로 변환합니다.

먼저 문자열을 왼쪽부터 순회하며 각 문자를 처리합니다. 피연산자(알파벳)는 바로 결과에 추가합니다.

여는 괄호 ‘(‘는 무조건 스택에 넣습니다. 닫는 괄호 ‘)’를 만나면 여는 괄호가 나올 때까지 스택에서 연산자를 꺼내 결과에 추가합니다.

연산자를 만나면 스택 최상단의 연산자와 우선순위를 비교합니다. 스택 최상단의 연산자가 현재 연산자보다 우선순위가 높거나 같으면 스택에서 꺼내 결과에 추가합니다. 이를 반복한 후 현재 연산자를 스택에 넣습니다.

모든 문자를 처리한 후 스택에 남은 연산자를 모두 결과에 추가하면 후위 표기식이 완성됩니다.

시간 복잡도는 O(N)입니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Text;

namespace Solution {
  class Program {
    static int Priority(char op) {
      if (op == '*' || op == '/')
        return 2;
      if (op == '+' || op == '-')
        return 1;
      return 0;
    }

    static void Main(string[] args) {
      var expr = Console.ReadLine()!;
      var ops = new Stack<char>();
      var sb = new StringBuilder();

      foreach (var ch in expr) {
        if (char.IsLetter(ch)) {
          sb.Append(ch);
        } else if (ch == '(') {
          ops.Push(ch);
        } else if (ch == ')') {
          while (ops.Peek() != '(')
            sb.Append(ops.Pop());
          ops.Pop();
        } else {
          while (ops.Count > 0 && Priority(ops.Peek()) >= Priority(ch)) {
            if (ops.Peek() == '(')
              break;
            sb.Append(ops.Pop());
          }
          ops.Push(ch);
        }
      }

      while (ops.Count > 0)
        sb.Append(ops.Pop());
      Console.WriteLine(sb.ToString());
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int priority(char op) {
  if (op == '*' || op == '/')
    return 2;
  if (op == '+' || op == '-')
    return 1;
  return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string expr; cin >> expr;
  stack<char> ops;
  string out;

  for (char ch : expr) {
    if (isalpha(static_cast<unsigned char>(ch))) {
      out.push_back(ch);
    } else if (ch == '(') {
      ops.push(ch);
    } else if (ch == ')') {
      while (!ops.empty() && ops.top() != '(') {
        out.push_back(ops.top());
        ops.pop();
      }
      if (!ops.empty())
        ops.pop();
    } else {
      while (!ops.empty() && priority(ops.top()) >= priority(ch) && ops.top() != '(') {
        out.push_back(ops.top());
        ops.pop();
      }
      ops.push(ch);
    }
  }

  while (!ops.empty()) {
    out.push_back(ops.top());
    ops.pop();
  }

  cout << out << "\n";

  return 0;
}