7. 수식을 읽는 순서를 스택에 맡긴다
해설글
작성 · 4분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
사람이 쓰는 수식을 컴퓨터의 실행 순서로 바꾸기
8-2-1의 값은 (8-2)-1=5이고, 8-(2-1)의 값은 7이다. 숫자와 연산자는 같지만 괄호가 실행 순서를 바꾼다. 원하는 결과는 입력 수식의 우선순위와 괄호를 잃지 않으면서 컴퓨터가 왼쪽부터 바로 계산할 수 있는 형태다.
연산자를 피연산자 사이에 쓰는 8-2를 중위식, 피연산자 뒤에 쓰는 82-를 후위식이라고 한다. 우선순위는 *를 +보다 먼저 처리하는 규칙이고, 연산자의 결합 방향은 같은 우선순위가 이어질 때 왼쪽과 오른쪽 중 어디부터 묶는지 정한다. 이는 값을 어떻게 묶어도 결과가 같은지를 말하는 수학의 결합법칙과 다른 개념이다. 보통 -와 /는 왼쪽부터 묶인다.
중위식을 읽는 동안 아직 출력할 수 없는 연산자를 스택에 보관한다. 후위식을 계산할 때는 숫자를 스택에 넣고, 연산자를 만나면 필요한 피연산자를 꺼내 결과를 다시 넣는다.
쉬워 보인 부분과 외우고 싶었던 부분
후위수식과 중위-후위 변환 노트에는 서로 다른 반응이 붙어 있다.
후위수식이란? 숫자는 스택에 넣고 연산자가 나오면 스택의 맨위의 두개를 pop해서 연산하는 것! → 이거 컴터로 연산하는건 쉽겠다.
중위수식을 후위수식으로 변환하는 과정은?? → 아 개어렵네 미치겠다 그냥 외워!
후위식 82-는 읽는 순서가 곧 계산 순서다. 8과 2를 push하고 -를 만나 두 값을 꺼낸다. 중위식 8-2는 연산자가 두 피연산자 사이에 있어 우선순위와 괄호를 먼저 해석해야 한다. 어려움의 차이는 스택 자체보다 언제 연산자를 실행할지에 있다.
두 번째 pop이 왼쪽 값이다
후위식 평가 코드는 뺄셈과 나눗셈에서 순서를 구분한다.
int right = pop(s);
int left = pop(s);
push(s, left - right); /* 나눗셈도 left / right */
나중에 push된 오른쪽 피연산자가 먼저 나온다. 덧셈과 곱셈은 순서를 바꿔도 결과가 같아 이 실수를 감춘다. 82-3/은 (8-2)/3=2, 82/3-은 (8/2)-3=1이다.
이번에 만든 수식 스택 검증 코드를 실행한 결과다.
8-2-1 -> 82-1- -> 5
8-(2-1) -> 821-- -> 7
2+3*4 -> 234*+ -> 14
invalid brackets rejected: true
왼쪽부터 묶이는 뺄셈과 괄호로 묶은 뺄셈이 서로 다른 후위식과 값이 되는지 확인했다. 여는 괄호 없이 닫히는 입력도 거부했다. 원본 괄호 코드의 “스택이 비었을 때 닫는괄호 나올 수 있음!”이라는 주석이 empty 검사를 두는 이유다.
중위식을 외우지 않고 읽기
중위식 변환에서는 피연산자는 곧바로 출력하고, 연산자는 잠시 스택에 둔다. +, -, *, /처럼 왼쪽부터 묶이는 연산자는 새 연산자를 만났을 때 top의 우선순위가 높거나 같으면 pop한다. 같은 우선순위의 연산자도 먼저 꺼내야 8-2-1이 (8-2)-1이 된다. 거듭제곱처럼 오른쪽부터 묶이는 연산자를 추가한다면 같은 우선순위일 때는 pop하지 않는 별도 조건이 필요하다.
8-2-1을 한 토큰씩 읽으면 다음처럼 움직인다.
| 읽은 토큰 | 출력 | 연산자 스택 |
|---|---|---|
8 |
8 |
비어 있음 |
첫 - |
8 |
- |
2 |
82 |
- |
둘째 - |
82- |
- |
1, 입력 끝 |
82-1- |
비어 있음 |
괄호가 있는 8-(2-1)에서는 여는 괄호가 바깥의 -와 안쪽 -를 분리하는 경계가 된다.
| 읽은 토큰 | 출력 | 연산자 스택 | 처리 |
|---|---|---|---|
8 |
8 |
비어 있음 | 피연산자를 바로 출력 |
바깥 - |
8 |
- |
연산자를 보관 |
( |
8 |
- ( |
여는 괄호를 경계로 보관 |
2 |
82 |
- ( |
피연산자를 바로 출력 |
안쪽 - |
82 |
- ( - |
괄호 안 연산자를 보관 |
1 |
821 |
- ( - |
피연산자를 바로 출력 |
) |
821- |
- |
(까지 pop하고 괄호는 버림 |
| 입력 끝 | 821-- |
비어 있음 | 남은 바깥 -를 출력 |
완성된 후위식 821--는 먼저 2-1을 계산하고 그 결과를 8의 오른쪽 피연산자로 사용하므로 7이 된다.
A + B * C
출력: A B C
스택: + 를 보관, *는 +보다 먼저 처리
결과: A B C * +
여는 괄호는 바깥 연산자와의 비교를 막는 경계다. 닫는 괄호가 오면 여는 괄호까지 pop하고 괄호 자체는 출력하지 않는다. 이렇게 보면 노트의 여섯 단계는 암기 목록이 아니라 “아직 실행하면 안 되는 연산자를 어디에 보관할까”에 대한 답이다.
원본 중위→후위 구현은 !, *, /, +, -, 비교와 논리 연산자의 우선순위도 다룬다. 다만 출력 배열 끝에 \0을 기록하지 않고 %s로 출력하므로 현재 코드는 정의되지 않은 동작이다. 변환을 마친 뒤 반드시 postfix[np] = '\0'을 넣어야 한다.
또 원본 평가기는 문자 하나를 숫자 하나로 보므로 다자리 수와 음수를 처리하지 않는다. 이것은 과제 범위일 수 있다. 범용 계산기로 확장하려면 문자 단위 순회 앞에 tokenizer가 필요하고, 0으로 나누기와 잘못된 괄호도 오류로 반환해야 한다.
이번에는 top이 “아직 처리할 차례가 오지 않은 연산자”와 “아직 짝을 못 찾은 여는 괄호”를 기억했다. 순서를 외우는 대신 스택에 남아 있는 값이 무엇을 기다리는지 읽으면 변환 과정이 한결 구체적으로 보인다.