[알고리즘] 전위(prefix), 중위(infix), 후위(postfix) 표기법 변환 및 계산

📚수식 표기법의 종류

1. 전위 표기법(prefix)

• 연산자가 피연산자 앞에 있는 표기법

  $+AB$

2. 중위 표기법(infix)

• 연산자가 두 피연산자 사이에 위치하는 표기법
• 평소 우리가 사용하는 방법

  $A+B$

3. 후위 표기법(postfix)

• 연산자가 피연산자 뒤에 위치하는 표기법
• 컴파일러가 사용하는 표기법

  $AB+$

그렇다면 왜 컴퓨터는 전위/후위표기법을 사용할까요?

$1 + 2 * 3 - 4 / 2$

우리는 위와 같은 중위표기식을 보면, 한 번에 수식 내에서의 우선순위를 고려하며 계산을 할 수 있습니다. 그래서 바로 $1 + 6 - 2 = 5$라는 답을 찾을 수 있습니다.

💻 : $1 + 2 = 3$이고, $3*...$ 엇? 곱하기가 먼저라 $1 + 2$로 계산하면 안되네?😭

하지만 컴퓨터는 앞에서부터 하나씩 읽어가면서 수식을 확인하기 때문에 우선순위에 따라 계산 순서가 달라지는 중위표기식은 구현하기 매우 복잡해집니다.

따라서 컴퓨터는 사람이 작성한 중위표기법을 전위/후위표기법으로 변환한 뒤 계산을 하게 됩니다.

후위 표기법의 장점

1. 괄호가 필요없습니다.
2. 연산자의 우선순위를 고려하지 않아도 됩니다.
3. 수식을 읽으면서 바로 계산할 수 있습니다.

🔄수식 표기법의 변환

수식 표기법의 변환과 후위 표기법에서 계산을 할 때는 모두 스택을 사용합니다.

저는 후위표기법을 중심으로 설명하도록 하겠습니다.

1. 중위 ➡ 후위

1. 피연산자(숫자나 변수 이름)가 들어오면, 그대로 바로 출력합니다.
2. 연산자가 들어오면, 그보다 우선순위가 높거나 같은 연산자들은 스택에서 pop한 뒤 새로 들어온 연산자를 push해줍니다.
3. 열린 괄호 (가 들어오면, 스택에 push합니다.
4. 닫힌 괄호 )가 들어오면, 스택에서 (가 나올 때까지 모두 pop해줍니다.
5. 모든 수식을 다 읽었다면, 스택에 남아있는 것들을 모두 pop해줍니다.

중위 ➡ 후위 예시

👩‍🏫 : $7 + 3 * (5 - 2) + 4$ 를 후위 표기법으로 바꿔보자!

변환 결과 : $7352-*+4+$

2. 후위 ➡ 중위

1. 피연산자(숫자나 변수 이름)는 스택에 push합니다.
2. 연산자를 만나면 연산자의 연산에 필요한 만큼의 피연산자를 스택에서 pop 하여 연산식을 변수로 치환하고, 치환된 변수를 다시 스택에 push 한다.
3. 수식이 끝나면 마지막 스택을 pop 하여 출력합니다.
4. 치환된 변수들을 다시 원래 식으로 바꾸어줍니다.

후위 ➡ 중위 예시

👩‍🏫 : $7352-*+4+$ 를 중위 표기법으로 바꿔보자!

변환 결과 :
$D\\= C + 4 \\= 7 + B + 4 \\= 7 + 3 * A + 4 \\= 7 + 3 * (5 - 2) + 4$

🧮후위 표기법의 계산

후위 표기법은 스택을 사용하여 앞에서부터 읽어가면서 쉽게 계산을 할 수 있습니다.

1. 피연산자를 만나면, 스택에 push합니다.
2. 연산자를 만나면, 스택에서 피연산자 2개를 pop하여 연산한 뒤 그 결과를 다시 스택에 push합니다.
3. 모든 연산을 마치고 스택에 남아있는 하나의 피연산자가 계산 결과입니다.

후위 표기법의 계산 예시

👩‍🏫 : $7352-*+4+$ 를 계산해보자!

💻코드

중위 ➡ 후위 변환 파이썬 구현

백준 1918번 후위 표기식 문제

import sys

expressions = sys.stdin.readline().strip()
stack = []
# 각 연산자 별 우선순위가 높거나 같은 연산자 모음 딕셔너리
op = {'+': ['+', '-', '*', '/'], '-': ['+', '-', '*', '/'], '*': ['*', '/'], '/': ['*', '/']}
# 각 연산자별 우선순위로, 아래와 같이 구현할 수도 있다.
# priority_map = {'+': 0, '-': 0, '*': 1, '/': 1, '(': -1} 

for ex in expressions:
    if ex.isalpha():
        print(ex, end='')
    elif ex == '(':
        stack.append(ex)
    elif ex == ')':
        tmp = stack.pop()
        while tmp != '(':
            print(tmp, end='')
            tmp = stack.pop()
    else:
        while stack and stack[-1] in op[ex]:
            print(stack.pop(), end='')
        stack.append(ex)

while stack:
    print(stack.pop(), end='')

후위 표기법 계산 파이썬 구현

백준 1935번 후위 표기식2 문제

import sys
input = sys.stdin.readline
N = int(input())
expressions = input().strip()
nums = [int(input()) for _ in range(N)]
stack = []

for ex in expressions:
    if ex.isalpha():
        stack.append(nums[ord(ex) - 65])
    else:
        a, b = stack.pop(), stack.pop()
        # result = eval(b + ops + a) #eval을 사용하여 계산할 수도 있다.
        if ex == '+':
            stack.append(b + a)
        elif ex == '-':
            stack.append(b - a)
        elif ex == '*':
            stack.append(b * a)
        elif ex == '/':
            stack.append(b / a)
print("%0.2f"%stack[-1])

Reference

[자료구조] 스택 응용 전위표기(PREFIX), 후위표기(POSTFIX), 중위표기(INFIX)

중위 표기법을 후위 표기법으로 변환후 계산하기

스택 자료구조의 활용 - 후위표기식

[자료구조] 중위표기식 < - >후위표기식 변환 방법(stack의 응용)

썸네일 출처 : GIPHY