[알고리즘 문제 풀기] 후위 표기식(1918)

1. 문제 풀이 아이디어

• 각 연산자의 우선순위에 따라 스택에 쌓고, 괄호를 만났을 때는 해당 괄호에 맞는 연산자들을 처리하여 후위 표기법으로 변환해 문제를 해결할 수 있다.

2. 나의 정답 코드

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

StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string s = sr.ReadLine();
    Stack<char> stack = new Stack<char>();
    for (int i = 0; i < s.Length; i++)
    {
        switch (s[i])
        {
            case '+':
            case '-':
                while (stack.Count > 0 && stack.Peek() != '(') sb.Append(stack.Pop());
                stack.Push(s[i]);
                break;
            case '*':
            case '/':
                if (stack.Count > 0 && stack.Peek() != '(' && stack.Peek() != '-' && stack.Peek() != '+') sb.Append(stack.Pop());
                stack.Push(s[i]);
                break;
            case '(':
                stack.Push(s[i]);
                break;
            case ')':
                while (stack.Peek() != '(') sb.Append(stack.Pop());
                stack.Pop();
                break;
            default:
                sb.Append(s[i]);
                break;
        }
    }
    while (stack.Count > 0) sb.Append(stack.Pop());
    sw.WriteLine(sb);
}

3. 정리

• +, - 연산자는 스택에서 우선순위가 높은 연산자를 먼저 sb에 추가한 후 자신을 스택에 넣는다.

• *, / 연산자는 우선순위가 높은 연산자가 있으면 이를 sb에 추가하고, 현재 연산자를 스택에 넣는다.

• (는 스택에 추가하여 연산자를 그룹화한다.

• )는 스택에서 (까지 연산자를 sb에 추가한 후 (를 제거한다.

• 피연산자는 그대로 sb에 추가한다.

• 스택에 남아 있는 연산자들을 모두 sb에 추가한 후, 후위 표기법으로 변환된 결과를 출력해 문제를 해결한다.