스택 - 후위 표기 수식

스택 - 후위 표기 수식 계산

후위 표기법 수식의 계산

• 수식을 왼쪽부터 시작해서 오른쪽으로 차례대로 읽어드리면서
• 피연산자가 나타나면, 스택에 넣어준다
• 연산자가 나타나면, 스택에 들어있는 피연산자를 두 개 꺼내어 연산을 적용하고, 그 결과를 다시 스택에 넣어둔다
• 위 과정을 반복하면 마지막에 모든 연산이 적용된 결과가 스택에 유일하게 남아 있게 된다.

예시

A B + C D + * 의 계산과정 == (A + B) * (C + D)

1. A 는 피연산자 이므로 스택에 넣는다. 현재 스택 상황 : A
2. B 는 피연산자 이므로 스택에 넣는다. 현재 스택 상황 : A // B
3. +는 연산자 이므로 스택에서 피연산자 두 개를 꺼내어 연산하고, 그 결과를 스택에 넣는다. 현재 스택상황 : A + B
4. C 는 피연산자 이므로 스택에 넣는다. 현재 스택 상황 : A + B // C
5. D 는 피연산자 이므로 스택에 넣는다. 현재 스택 상황 : A + B // C // D
6. +는 연산자 이므로 스택에서 피연산자 두 개를 꺼내어 연산하고, 그 결과를 스택에 넣는다. 현재 스택 상황 : A + B // C + D
7. *는 연산자 이므로 스택에서 피연산자 두 개를 꺼내어 연산하고, 그 결과를 스택에 넣는다. 현재 스택 상황 : (A+B) * (C + D)
8. 수식이 끝났기 때문에 스택에 남아있는 최종 연산 결과를 꺼낸다

알고리즘의 설계

• 후위 표현식을 왼쪽부터 한 글자씩 읽어서
  • 피연산자이면, 스택에 push
  • 연산자를 만나면 스택에서 pop → (1), 또 pop → (2)
  • (1) 연산 (2) 을 계산 이 결과를 스택에 push
• 수식의 끝에 도달하면, 스택에서 pop → 이것이 계산 결과