1. 전위, 중위, 후위 표기식
  2. 중위 표기식에서 후위 표기식으로의 변환
  3. 풀이
  4. 추가) 후위 표기식의 연산

전위, 중위, 후위 표기식

Prefix, Infix, Postfix Expression

일반적인 수식은 피연산자와 피연산자 사이에 연산자를 위치시킨다. A와 B를 더하는(+)연산을 기술할 때 A+B로 표현하듯이 말이다. 연산자를 피연산자들의 앞에 위치시키거나 뒤에 위치시키는 표기 방법을 각각 전위 Prefix, 후위 Postfix 표기식이라고 하며, 앞의 예시는 각각+AB, AB+로 쓸 수 있다.

중위 표기식에서 후위 표기식으로의 변환

피연산자는 그 상대적인 위치가 바뀌지 않으므로, 연산자만 위치를 바꿔서 넣어주면 된다. 그러기 위해 연산자를 담아놓는 스택을 하나 만들어서, 입력된 연산자를 추가하거나 제거하면서 진행한다.

  1. 입력된 수식을 문자열로 저장하고, 출력용 문자열을 빈 문자열로 초기화한다. 연산자를 담기 위한 opstack을 초기화한다.
  2. 입력 문자열을 앞에서부터 하나의 문자씩 접근한다.
    1. 문자가 피연산자인 경우, 출력용 문자열에 추가한다.
    2. 문자가 왼쪽 괄호 ‘(‘인 경우, opstack에 push한다.
    3. 문자가 오른쪽 괄호 ‘)’인 경우, 대응하는 왼쪽 괄호 ’(‘가 나올 때 까지 opstack에서 연산자를 pop하고 문자열에 추가한다.
    4. 문자가 연산자인 경우, opstack에 push한다. 그 전에, 이미 opstack에 있는 연산자들 중 우선순위가 높거나 같은 것들을 모두 pop한 후 문자열에 추가한다.
  3. 입력 문자열을 모두 읽었다면 opstack에 남아있는 연산자를 차례대로 pop하고 문자열에 추가한다.

처음 문제를 접근했을 때는 어떤 경우에 연산자를 하나 pop하거나 여러개를 pop해야 하는지 기준을 생각하지 못했었는데, 위의 과정 중 2-4에 그 답이 있다. 연산자의 우선순위를 딕셔너리 형식으로 저장해서, 곱셈과 나눗셈을 먼저 끝낼 수 있도록 했다.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
eq = input().strip()
posteq = ''
opstack = []
opdic={'(':1, '+':2, '-':2, '*':3, '/':3}
for i in eq:
    if i.isalpha():
        posteq += i
    elif i=='(':
        opstack.append(i)
  elif i==')':
    while opstack:
      operator = opstack.pop()
      if operator == '(':
        break
      posteq += operator
  else:
    while opstack and opdic[opstack[-1]] >= opdic[i]:
      posteq += opstack.pop()
    opstack.append(i)
while opstack:
  posteq += opstack.pop()
print(posteq)

추가) 후위 표기식의 연산

우리에게 친숙한 중위표기식은 연산하기 쉽지만, 후위 표기식으로 변환된 경우 직관적이지 않다. 이 때도 스택 자료구조를 사용한다.
앞에서부터 문자를 하나씩 접근해서 피연산자라면 스택에 push하고, 연산자라면 스택에서 두 개의 피연산자를 pop한 후 연산한 결과를 다시 push한다.
예를 들어, 4 5 6 * +의 후위표기식이 있다고 하자. 스택에 담긴 데이터는 아래와 같은 순서로 변하면서 마지막에는 최종 결과값만 남아있게 된다.

  • 4 + 5
  • 4 5 + 6
  • 4 5 6 + *
  • 4 30 + +
  • 34

참고자료
Problem Solving with Algorithms and Data Structures using Python, Chapter 4.9.