[1918] - 후위 표기식

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

접근 방법

중위 표기식에서 후위 표기식 만들 때 규칙

1.  피연산자 만나면 그대로 출력
2.  연산자를 만나면 스택에 저장
   • 이 때, 스택의 연산자가 들어오는 연산자보다 우선순위가 크거나 같으면 -> 스택의 연산자 꺼내고 입력된 연산자 넣기
3.  오른쪽 괄호(닫는 괄호)가 나오면 왼쪽 괄호 위에 쌓여있는 모든 연산자 꺼내기

 

문제 풀이

• 출력할 리스트와 스택을 생성
• 피연산자 - 알파벳들을 만나면 리스트에 add
• 연산자를 만나면 위 후위표기식 만드는 규칙에 따라서 적용
• 마지막 스택에 남아있는 연산자들 꺼내고 출력

 

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

namespace Baekjoon.Gold
{
    class _1918
    {
        static void Main(string[] args)
        {
            char[] c = Console.ReadLine().ToCharArray();
            List<char> list = new List<char>();
            Stack<char> stack = new Stack<char>();

            for(int i = 0; i<c.Length; i++)
            {
            	//알파벳이면 리스트 넣기
                if (c[i] != '+' && c[i] != '-' && c[i] != '*' && c[i] != '/' && c[i] != '(' && c[i] != ')')
                    list.Add(c[i]);
                else
                {
             		//여는 괄호면 넣기
                    if (c[i] == '(')
                        stack.Push(c[i]);
                    //+, -면 안에 ( 나올때까지 pop 후 리스트 추가
                    else if (c[i] == '+' || c[i] == '-')
                    {
                        while (stack.Count > 0)
                        {
                            if (stack.Peek() == '(')
                                break;
                            list.Add(stack.Pop());
                        }


                        stack.Push(c[i]);
                    }
                    //*, / 이면 (, 우선순위가 낮은거 나올때 까지 pop 리스트 추가
                    else if (c[i] == '*' || c[i] == '/')
                    {
                        while (stack.Count > 0)
                        {
                            if (stack.Peek() == '(' || stack.Peek() == '+' || stack.Peek() == '-')
                                break;
                            list.Add(stack.Pop());
                        }

                        stack.Push(c[i]);
                    }
                    // )면 여는괄호 나올 때까지 pop 리스트 추가 
                    else if (c[i] == ')')
                    {
                        while (stack.Count > 0)
                        {
                            if(stack.Peek() == '(')
                            {
                                stack.Pop();
                                break;
                            }
                            list.Add(stack.Pop());
                        }
                    }
                }
            }
            //남은 연산자들 꺼내기
            while (stack.Count > 0)
                list.Add(stack.Pop());

            Console.WriteLine(string.Join("", list));
        }
    }
}