[알고리즘 과제] 스택의 응용: 사칙연산

( 117.32 + 83 ) * 49

 

1. 중위 표기식(In-order)을 후위 표기식(Post-order)으로 변환하는 과정

• 연산자 또는 여는 괄호를 만나면 스택에 PUSH한다.
• 피연산자를 만나면 즉시 출력한다.
• 닫는 괄호를 만나면 여는 괄호를 POP할 때 까지 계속 POP한다. 연산자를 POP할 때는 동시에 출력한다.
• 수식의 끝에 도달하면, 스택이 EMPTY 될 때 까지 계속 POP한다. 연산자를 POP할 때는 동시에 출력한다.

	여는 괄호를 만남 → 스택에 PUSH
	피연산자 '117.32'를 만남 → 출력
	연산자 '+'를 만남 → 스택에 PUSH
	피연산자 '83'를 만남 → 출력
	닫는 괄호를 만남 → 닫는 괄호부터 여는 괄호까지 순서대로 스택에서 POP → 연산자는 POP 하면서 동시에 출력
	연산자 '*'를 만남 → 스택에 PUSH
	피연산자 '49'를 만남 → 출력
	수식의 끝에 도달함 → 스택이 EMPTY 될 때까지 POP → 연산자는 POP 하면서 동시에 출력

 

2. 후위 표기식(Post-order) 계산 과정

• 피연산자를 만나면 만나면 스택에 PUSH한다.
• 연산자를 만나면 POP을 두 번 수행한다. POP한 두 피연산자를 연산한 결과값을 스택에 PUSH한다. 
• 수식의 끝에 도달하면, 최종 연산 결과값이 스택에 저장된다. 

	피연산자 '117.32'를 만남 → 스택에 PUSH
	피연산자 '83'를 만남 → 스택에 PUSH
	연산자 '+'를 만남 → 스택 POP을 두 번 수행함 → POP한 두 피연산자로 연산 수행(83 + 117.32) → 연산 결과(200.32)를 스택에 PUSH
	피연산자 '49'를 만남 → 스택에 PUSH
	연산자 '*'를 만남 → 스택 POP을 두 번 수행함 → POP한 두 피연산자로 연산 수행(49 * 200.32) → 연산 결과(9815.68)를 스택에 PUSH
	수식의 끝에 도달함 → 최종 연산 결과가 스택에 저장되어 있음

 

 

[참고] 연산식의 중위, 전위, 후위 순회 예시(자료구조 과제)