[스택] 후위표기식

📍 후위표기식
연산자가 피연산자 뒤에 있는 표기식

A+(B*C) -> ABC*+
: 연산자는 stack 에 append() 하거나 pop() 하고 피연산자는 그대로 출력하여 해결한다.

 

 

<input>

3+5*2/(7-2)

 

 

✔️ code

 

import sys
sys.stdin=open("input.txt", "rt")

arr=input()
operator=['+', '-', '*', '/', '(', ')']
stack=[]    #연산자를 담는 stack
result=''   #후위표기식

for x in arr:
    if x not in operator:
        result+=x
    else:
        if x=='(':
            stack.append(x)
        elif x=='*' or x=='/':
            while stack and (stack[-1]=='*' or stack[-1]=='/'):
                result+=stack.pop()
            stack.append(x)
        elif x=='+' or x=='-':
            while stack and stack[-1]!='(':
                result+=stack.pop()
            stack.append(x)
        elif x==')':
            while stack[-1]!='(':
                result+=stack.pop()
            stack.pop()
while stack:
    result+=stack.pop()
print(result)

 

#solve:

352*72-/+ 가 출력되어야 한다.

우선순위가 같은 +,- 와 *,/ 를 함께 조건식으로 묶어주었고

* 나 / 가 나왔을 때 stack 에 있는 값보다 우선순위가 높다면 stack 에 append() 하지만,

stack 에 * 나 / 가 stack[-1] 이라면 이를 먼저 연산해야하므로 pop() 해준다.

+ 나 - 가 나오면 stack[-1] 이 '(' 가 아닌 이상 우선순위가 가장 낮으므로 pop() 을 수행하고,

stack[-1] == '(' 라면 stack 에 append() 가 가능하다.

'(' 연산자는 ')' 가 나올 때까지 대기하고 만약 x==')' 라면 '(' 내부 연산자를 먼저 pop() 해준 뒤,

마지막으로 '(' 을 pop() 해준다.

남은 연산자는 index:-1 ~ 부터 0까지 result 에 추가해주면 된다.

 

 

 

>>>

best code를 보니 연산자를 구분하기 위한 배열을 따로 설정하지 않고 isdecimal() 을 사용할 수 있었다.

그동안 잘 써먹지 않아서 까먹고 있었다 만약 연산자가 훨씬 많았다면 위 코드처럼 따로 배열을 설정하는 것에 한계가 있을테니, isdecimal() 을 잘 활용해야겠다.