Stack 예시 - 계산기 코드 작성

"2+3 5"
-> 피연산자 연산자 구별 2 + 3 5
-> 연산자 우선순위 (2+(3* 5))
-> 계산 17

연산자 :
이항 연산자(2+3) , 단항 연산자(+3)

여기서는 이항 연산자만 있다고 가정.

Idea : infix수식(2+3 5) -> postfix수식(2 3 5 +) 으로 변경

1) 괄호치기 (2+(3 5))
2) 연산자의 오른쪽 괄호로 연산자 이동 (2 (3 5) )+
3) 괄호 지우기 2 3 5 * +

자 이제 이를 토대로 문제 시작!

입력 : +,-,* ,(,),숫자로 구성된 infix수식
출력 : posfix 수식

일단 피연산자의 순서는 변화하지 않을 것
a+b c -> a b c + : 더하기는 가 뒤에 있나 확인해야 함
a b+c -> a b c + : 는 일단 나오면 stack, 그 다음 +가 나오면 * 빼고 + push

즉 자기보다 우선순위가 들어가있으면 pop하고 자기가 들어간다. 만약 없으면 자신이 push되어 들어간다.(왼쪽 괄호 < + < * < 오른쪽 괄호)

(a+b) c -> ( 들어가고, a 적고, +넣고, b적고, )가 등장하면 (가 나올 때 까지 pop(즉 괄호 안부터 계산한다.), push하고 c적고 마지막에
: a b + c

이렇게 마지막에 최종 출력되는 것을
리스트:outstack
스택은: opstack

for each token in expr:
	if token == operand:
    	outstack.append(token)
    elif token == '(':
    	opstack.push(token)
    elif token == ')':
    	opstack에 저장된 연산자 '('를 pop할 때 까지 pop
        그 다음 outstack에 모두 append
    elif token in + * - / :
    	opstack의 token들 중 자신보다 우선순위가 높은 연산자 모두 pop
        그 다음 자신이 push
 
outstack에 남은 연산자 모두 pop -> outstack에 append

이렇게 infix를 posifx로 바꿨다면, 이제는 무엇을 해야 할까?

6 3 2 - 4 * +

S = Stack()
1) if token == operand
	S.push(token)
2) if token in + - * /:
	a = S.pop
    b = S.pop
    c = b token a
    S.push(c)

https://www.youtube.com/watch?v=MYk4autDAJ0&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=10