Infix Notation & Postfix Notation (중위 & 후위 표기법)

✅ Infix Notation & Postfix Notation (중위 & 후위 표기법)

표기법	표현 방식	예제	후위변환 결과
중위 표기법	연산자가 피연산자 사이	3 + 5 * 2	3 5 2 * +
후위 표기법	연산자가 피연산자 뒤	3 5 2 * +	계산 결과: 13

✔️ 후위 표기법은 괄호 없이도 연산 순서가 명확해짐
✔️ 스택을 이용하면 간단하게 구현 가능

 

중위 표기법 (Infix Notation)

• 우리가 일반적으로 사용하는 수식 표현 방식
• 연산자가 피연산자 사이에 위치
• 예시: 3 + 5 * 2 → (5 * 2 먼저 계산)

 

후위 표기법 (Postfix Notation, Reverse Polish Notation - RPN)

후위표기법 계산

• 연산자가 피연산자 뒤에 위치
• 괄호 없이 연산 순서를 명확히 표현 가능
• 예시: 3 5 2 * + → (5 × 2 먼저 계산 후 3 더하기)

---

✅ 중위 표기식 → 후위 표기식 변환 (Shunting-Yard 알고리즘)

 

 

• 연산자 우선순위
  • *와 /는 +와 -보다 우선순위가 높다.
  • 같은 우선순위의 연산자는 왼쪽에서 오른쪽으로 처리.
• 변환 규칙
  • 숫자(피연산자)는 그대로 출력
  • 연산자는 스택에 넣되, 우선순위가 높은 연산자가 나오면 기존 연산자를 먼저 출력
  • 괄호 (는 스택에 넣고, )를 만나면 (가 나올 때까지 스택에서 꺼내 출력
  • 마지막에 남은 연산자들은 모두 출력

 

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}  # 연산자 우선순위
    output = []  # 후위 표기식 결과 저장
    operators = []  # 연산자 스택

    tokens = expression.split()  # 공백 기준으로 토큰 분리

    for token in tokens:
        if token.isnumeric():  # 숫자는 그대로 출력
            output.append(token)
        elif token in precedence:  # 연산자인 경우
            while (operators and precedence.get(operators[-1], 0) >= precedence[token]):
                output.append(operators.pop())  # 우선순위가 높거나 같은 연산자는 먼저 출력
            operators.append(token)  # 현재 연산자를 스택에 추가
        elif token == '(':  # 여는 괄호는 스택에 push
            operators.append(token)
        elif token == ')':  # 닫는 괄호를 만나면
            while operators and operators[-1] != '(':
                output.append(operators.pop())  # 여는 괄호가 나올 때까지 출력
            operators.pop()  # 여는 괄호 제거

    while operators:  # 스택에 남아 있는 연산자 출력
        output.append(operators.pop())

    return ' '.join(output)  # 리스트를 문자열로 변환하여 반환

# 예제 실행
expr = "3 + 5 * ( 2 - 8 )"
postfix = infix_to_postfix(expr)
print(postfix)  # 출력: 3 5 2 8 - * +

1. "3 + 5 * ( 2 - 8 )" → 공백 기준으로 토큰화

     ['3', '+', '5', '*', '(', '2', '-', '8', ')']

✅Shunting-Yard 알고리즘 과정

토큰	출력(후위표기식)	스택(연산자)
3	3	[]
+	3	['+']
5	3 5	['+']
*	3 5	['+', '*']
(	3 5	['+', '*', '(']
2	3 5 2	['+', '*', '(']
-	3 5 2	['+', '*', '(', '-']
8	3 5 2 8	['+', '*', '(', '-']
)	3 5 2 8 -	['+', '*']
끝	3 5 2 8 - * +	[]

 

---

✅ 후위 표기식 → 계산하기 

후위 표기법 계산 규칙

1. 피연산자(숫자)를 만나면 스택에 push
2. 연산자를 만나면 스택에서 필요한 숫자(pop)하여 연산 후 결과를 다시 push
3. 수식이 끝나면 스택에서 pop하여 최종 결과 출력

def evaluate_postfix(expression):
    stack = []

    for token in expression.split():
        if token.isnumeric():  # 숫자라면 스택에 push
            stack.append(int(token))
        else:  # 연산자라면 스택에서 숫자 두 개 pop
            b = stack.pop()  # 두 번째 피연산자 (뒤쪽)
            a = stack.pop()  # 첫 번째 피연산자 (앞쪽)
            
            # 연산 수행 후 결과를 다시 스택에 push
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)

    return stack.pop()  # 최종 결과 반환

# 테스트
expr = "3 5 2 8 - * +"  # 후위 표기법 수식
print(evaluate_postfix(expr))  # 출력: 3 + (5 * (2 - 8)) = 3 + (5 * -6) = 3 - 30 = -27

 

✅계산 과정

스텝	토큰	스택 변화	설명
1	3	[3]	숫자라서 push
2	5	[3, 5]	숫자라서 push
3	2	[3, 5, 2]	숫자라서 push
4	8	[3, 5, 2, 8]	숫자라서 push
5	-	[3, 5, -6]	2 - 8 = -6, push
6	*	[3, -30]	5 * -6 = -30, push
7	+	[-27]	3 + (-30) = -27, push

 

후위 표기법(Reverse Polish Notation, RPN)을 왜 사용할까? 🤔

후위 표기법을 쓰는 이유는 연산 우선순위를 명확하게 표현할 수 있기 때문이에요.
즉, 괄호 없이도 연산 순서를 확실하게 정할 수 있어서 컴퓨터가 계산하기 쉽습니다.

후위 표기법을 사용하면 연산자 우선순위나 괄호를 고려할 필요가 없음!

• 중위 표기법 → 연산자 우선순위를 따져야 함
• 후위 표기법 → 그냥 스택만 사용하면 해결됨! (컴퓨터가 계산하기 쉬움)