[파이썬] 백준1918 후위표기식 python

www.acmicpc.net/problem/1918

1918번: 후위 표기식

우선 후위표기식에 대해서 이해가 필요함.

그리고 사칙연산의 우선순위에 대해서 알아 둬야한다.

문제에서는 +, -, *, /, (, ) 와 알파벳 대문자만 사용한다.

우선순위

1. ( , )

2. * , /

3. + , -

 

그리고 같은 우선순위에 있는 연산자의 경우 왼쪽의 연산자부터 처리하면 된다.

 

스택을 활용해서 구현할 수 있는데.

문제에서는 알파벳을 사용하므로 

isalpha() 메서드를 사용해서 알파벳을 구분한다.

알파벳이 들어오면 결과값 문자열에 추가해주고

연산자가 들어오면 우선순위에 맞게 처리를 해준다.

 

리스트에 식전체를 넣어 for문을 통해 한 문자씩 확인한다.

1. () 를 확인한다.

2.  * /인지를 확인하고 먼저 들어온, 같은 우선순위에 있는 * / 는 모두 결과문자열에 추가해준다.

3. 그리고 현재 문자를 다시 스택에 추가

4. +, - 인지 확인한다. + ,- 는 이들보다 낮은 우선순위의 연산자가 없으므로 자신보다 우선순위가 높은 것들을 모두 

결과 문자열에 추가해준다.

5. ) 를 발견하면 ( 와 ) 사이에 있는 모든 연산자들을 결과문자열에 추가하고 (를 pop해준다.

그리고 마지막으로 남아있는 stack을 pop하며 결과문자열에 추가해주면 끝.

 

strn = list(input())
stack=[]
res=''
for s in strn:
    if s.isalpha():
        res+=s
    else:
        if s == '(':
            stack.append(s)
        elif s == '*' or s == '/':
            while stack and (stack[-1] == '*' or stack[-1] =='/'):
                res += stack.pop()
            stack.append(s)
        elif s == '+' or s == '-':
            while stack and stack[-1] != '(':
                res+= stack.pop()
            stack.append(s)
        elif s == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack :
    res+=stack.pop()
print(res)