후위표기식

백준 1918

후위표기식 구하기.

• 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다.
• 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.
• 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다.
• 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다.
• 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

입출력

입력	출력
A*(B+C)	ABC+*

---

접근 방식

: 입력값 전체에 괄호를 치고 알파벳이면 출력. 연산자이면 스택에 넣고 )를 만날 때마다 연산자 pop해서 출력 ---> 틀렸습니다.

알게된 점

주어진 입력값이 친절하게 괄호가 모두 있는 게 아니므로, 연산자 우선순위를 고려해야 한다.


1. 알파벳이면 출력한다.
2. (를 만나면 스택에 넣는다.
3. )를 만나면 (가 나올때까지 출력한다(연산자).
4. 연산자를 만났을 때, 스택의 top원소의 우선순위와 연산자의 우선순위를 비교하여, 연산자의 우선순위가 작거나 같을 동안 스택의 원소를 pop하여 출력하고 연산자를 스택에 넣어준다. 만약 크다면 바로 스택에 넣어준다.
5. 마지막으로 스택에 남아있는 연산자를 출력한다.

코드

string = input()

priority = {'*': 2, '/': 2, '+': 1, '-': 1, '(': 0}

ans = ''
stack = []
for s in string:
    if s.isalpha():
        ans += s
    elif s == '(':
        stack.append(s)
    elif s == ')':
        while stack and stack[-1] != '(':
            ans += stack.pop()
        stack.pop()
    else:
        while stack and priority[s] <= priority[stack[-1]]:
                ans += stack.pop()
        stack.append(s)

while stack:
    ans += stack.pop()
print(ans)