[자료구조] 15 수식의 평가 ( 중위, 후위, 전위 표기법 )

📌 수식( Expression )의 구성

연산자 ( Operator ) + 피연산자  ( Operand )

 

✔️ 연산자의 종류

산술 ( Arithmetic )

논리 ( Logical )

대입 ( Assignment )

 

✔️ 피연산자의 종류

변수 ( Variable )

상수 ( Constant )

 

👉 수식의 표기법은 피연산자에 대한 연산자의 위치에 따라 나뉜다 

표기법	수식
중위 표기법 ( Infix )	a / b - c + d * e - a * c
후위 표기법 ( Postfix )	a b / c - d e * + a c * -
전위 표기법 ( Prefix )	- + - / a b c * d e * a c

 

❗️ 중위 표기법

-수식 안에 여러개의 연산자가 존재할 경우 

-각 연산자의 연산 순위가 높은 부분이 우선적으로 계산 된다. 

-동일 연산 순위라면 결합성 규칙에 의해 결정된다 

 

중위 표기법 ( Infix )	후위 표기법 ( Postfix )
순서 : Operand Operator Operand 각 연산자 별 우선 순위가 존재, 괄호를 사용하여 우선순위 변경 가능 복잡한 계산 순서 사람이 이해하기는 쉽지만 프로그래밍이 복잡	순서 : Operand Operand Operator 연산자의 우선순위 없음, 괄호 사용하지 않음 왼쪽 => 오른쪽 방향으로 계산,  프로그래밍이 쉬우나 사람이 이해하기 어려움
5 + 9 * 7	5 9 7 * +
a * b + c	a b * c +
( 2 + 3 ) * 7	2 3 + 7 *

 

 

 

 

✔️ 후위 수식 알고리즘 

1. 수식을 왼쪽에서 오른쪽으로 스캔

2. 수식에서 들어온 입력이 피연산자인 경우 스택에 넣기

3. 입력이 연산자인경우 스택에서 피연산자 2개 꺼내기

4. 꺼낸 2개 계산한 후 결과 값 스택에 넣기 

👇👇👇

입력	stack[0]	stack[1]	stack[2]	top
5	5			0
7	5	7		1
*	35			0
9	35	9		1
+	44			0
3	44	3		1
4	44	3	4	2
/	44	0		1
-	44			0

* , / , + , - 등 연산자가 들어오면 그전에 들어온 피연산자 2개를 스택에서 꺼내서 연산자와 함께 계산

 

 

 

✔️ 중위수식에서 후위 수식으로 변환하는 알고리즘 

1. 입력이 피연산자이면 그대로 출력

2. 입력의 우선순위를 파악해야 한다

-스택 top의 연산자보다 우선순위가 높거나 스택이 비어 있을 경우 입력을 스택에 넣는다

-스택 topd보다 우선순위가 낮거나 혹은 같을 경우 스택을 pop하여 입력을 스택에 넣는다

3. 입력이 '(' 이면 ')'가 들어올 때 까지 다음 연산자를 1,2의 규칙에 따라 스택에 넣는다

4. 입력이 ')'이면 '('가 나올 때 까지 스택에서 계속 연산자를 pop하여 출력하고 '('은 출력하지 않고 버린다

5. 입력이 문자열의 끝 eos라면 스택의 모든 연산자를 꺼내서 출력한다 

 

 

a + ( b * c + d ) * e 

👇👇👇

입력	출력	스택
a	a
+	a	+
(	a	+ (
b	a b	+ (
*	a b	+ ( *
c	a b c	+ ( *
+	a b c *	+ ( +
d	a b c *  d	+ ( +
)	a b c * d +	+
*	a b c * d +	+ *
e	a b c * d + e * +