백준 1918. 후위 표기식
https://www.acmicpc.net/problem/1918
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
(윤성우의 자료구조)에서 스택 공부할때 나왔던 내용이다.
https://tose33.tistory.com/635
Chap06. 스택, 계산기 프로그램 구현
스택은 자료구조의 구현 자체보다는 스택을 활용한 알고리즘의 설계가 중요하다. 스택 자료구조를 이용해 다음과 같은 연산 처리가 가능한 계산기 프로그램을 구현한다. 1 + (2 +3) / 4 이는 단순
tose33.tistory.com
그런데 사실 위에 나와있는 내용은 책에도 아마 나와있었던 것 같은데 좀 단순화시킨 내용이었던것 같다.
스택을 이용하는데 중요한건 연산자들의 우선순위를 생각해야 한다.
+, - 는 스택에 넣을때 우선순위가 가장 낮기 때문에 이미 스택에 있는 연산자들은 나보다 무조건 크거나 같을 것이다.
따라서 이미 스택에 있는 연산자들은 나보다 먼저 계산되어야 하기 때문에 스택이 비거나 '('이 나올때까지 스택에서 모두 순서대로 top 부터 빼서 결과에 붙여주면 된다. (스택은 first in last out)
*, / 은 스택에 넣을때 이미 스택에 있는 연산자들은 나보다 작거나 같을 것이다.
하지만 나와 같은 우선순위인 *, - 은 나보다 먼저 들어갔으므로 먼저 계산되어야 한다.
따라서 *, - 들은 빼서 결과에 붙여주고 나를 스택에 푸쉬해준다.
( 은 스택에 그냥 넣어준다.
) 은 괄호 사이의 값들은 먼저 계산해줘야 되기 때문에 스택에서 ( 를 만날때까지 다 빼서 결과에 붙여주면 된다.
처음에 햇갈렸던 점은 미리 괄호를 다 삽입해놔야 하나 고민했다.
그런데 위 방식으로 하면 +,- 가 왔을때 스택이 비거나 '('이 나올때까지 모두 스택에서 빼서 결과에 붙여주기 때문에 그럴 필요는 없다.
스택은 First in Last out 인 것을 잘 생각해 보자.