스택의 응용 - 수식의 후위 표기법

중위 표기법(Infix Notation)

• 연산자가 피연산자들의 사이에 위치
• (A + B) * (C + D)

후위 표기법(Postfix Notation)

• 연산자가 피연산자들의 뒤에 위치
• AB + CD + *

예시

A * B + C

• 연산을 만나면 스택에 집어 넣는다
• 스택에 있는 연산자는 아직 표현되지 못한 연산자들이다.
• 을 스택에 저장 하고 나서, +를 만나면 우선순위가 가 높기 때문에 *는 스택에서 탈출한다. 즉, 스택안에서 우선순위가 유지되어야 하고 유지 되지 못하면 pop을 하게 된다.

A + B * C

• '+'을 넣고 나서, ''연산자를 만났을 때, 우선순위가 가 높기 때문에 일단 스택에 저장한다. *을 넣어도 우선 순위가 유지되기 때문에 일단 넣고 본다.

A + B + B

• 동일한 연산자를 만나게 되면 우선순위가 깨졌다고 판단하고, 스택에서 pop 을 한다.

괄호의 처리

예시1

[중위] (A + B) * C

[후위] A B + C *

• 여는 괄호는 스택에 push
• 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop

→ 괄호안에 있는 내용들 먼저 pop

예시2

[중위] A * (B + C)

[후위] A B C + *

• 연산자를 만났을 때, 여는 괄호 너머까지 pop 하지 않도록

• 여는 괄호 우선순위는 가장 낮게 설정

알고리즘의 설계

• 연산자의 우선순위 설정

prec = {
	'*' : 3,
	'/' : 3,
	'+' : 2,
	'-' : 2,
	'(' : 1 # 괄호는 우선 순위가 가장 낮게
}

• 중위 표현식을 왼쪽부터 한 글자씩 읽어서

  • 피연산지연 그냥 출력

  • (이면 스택에 push

  • ) 이면 ) 이 나올 때까지 스택에서 pop 그리고 출력

  • 연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop그리고 출력

    • 그리고 이 연산자는 스택에 push

• 스택에 남아 있는 연산자는 모두 pop 그리고 출력