9강 자료구조 스택 활용 - 계산기 2

infix -> postfix 변환 방법
왼쪽괄호 ( 는 우선순위가 가장 낮다.
오른쪽활호 ) 는 우선순위가 가장 높다.

결과값은 리스트 ouststack에 넣고 연산자는 스택 opstack에 넣었다가 oustack으로 옮긴다.

피연산자가 나오면 바로 outstack에 넣고, 연산자가 나오면 opstack에 넣는데 자신보다 우선순위가 높은게 opstack 안에 있다면 pop시키고 push한다. (는 그냥 들어가지만 )가 들어갈 차례가 오면 (가 나올때까지 pop하고, pop된건 outstack에 넣는다.
아래 코드는 pseudo 코드이다

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

좋은 웹페이지 즐겨찾기