계산기에서 Stack을 활용하는 방법

Intro

stack 을 활용하면 infix notation을 postfix notation으로 변환할 수 있다.

1972년에 도입된 최초의 휴대형 계산기 HP-35는 postfix notation을 기반으로 계산한다.

당시에 괄호를 처리하는게 어려웠기 때문이다. 

일단 postfix notation으로 변환하고 나면 계산기 입장에서는 계산이 쉬워진다.

 

• 왼쪽부터 차례대로 읽는다. (Read the expression from left to right)
• 현재 요소가 피연산자(숫자)이면 스택에 넣는다. (If current element is a value (e.g. Integer) push it to the stack)
• 연산자(operator)이면 마지막 두 요소를 꺼내 (pop last two operands from stack)
• 연산하고 다시 그 결과를 스택에 넣는다. (apply operator and push the result back to the stack)

 

RPN evaluation using stack ( https://f-o.org.uk/ )

 

문자열 수식 계산법

1. 중위표기법 수식을 스택을 이용하여 후위표기법으로 변환한다. (알고리즘)

 

중위표기법(infix notation)이란?

연산자를 피연산자의 가운데 표기하는 방법 ex. A+B

 

2. 후위표기법의 수식을 스택을 이용하여 계산한다.

 

후위표기법(postfix notation)이란?

연산자를 피연산자 뒤에 표기하는 방법 ex. AB+

 

 

중위표기식 -> 후위표기식 변환 방법

1. 입력받은 중위표기식에서 토큰을 읽는다.

2. 토큰이 피연산자(숫자)이면 토큰을 출력한다.

3. 토큰이 연산자(괄호, 사칙연산자)일 경우

    1. 우선순위가 높으면 스택에 push 한다.

    2. 우선순위가 높지 않으면 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop한 후 토큰의 연산자를 push한다.

    3. 만약 top에 연산자가 없으면 push한다.

4. 토큰이 오른쪽 괄호 ')'일 경우

    1. 스택 top에 왼쪽 괄호 '('가 올 때까지 스택에 pop연산을 수행한다.

    2. pop한 연산자를 출력한다.

    3. 왼쪽 괄호를 만나면 pop만 하고 출력하지는 않는다.

5. 중위표기식에 더 읽을 것이 없다면 중지하고, 더 읽을게 있다면 1부터 반복한다.

6. 스택에 남아있는 연산자를 모두 pop하여 출력한다.

 

 

우선순위

토큰	ISP (in-stack priority)	ICP (in-coming priority)
)	-	-
*, /	2	2
+, -	1	1
(	0	3

if (icp > isp) push()
else  pop()

 

예시

(6 + 5 * (2 - 8 ) / 2)    ===>    6528 - * 2 / +

 

1. 중위표기법 수식을 스택을 이용하여 후위표기법으로 변환한다. (알고리즘)

(6 + 5 * (2 - 8 ) / 2) 

숫자냐, 숫자가 아니냐로 구분하자.

숫자이면 바로 출력하고 숫자가 아니면 스택의 top과 비교해야 한다.

( 여는 괄호는 ICP 우선순위가 가장 높으므로 항상 push하고 그 외의 연산은 비교한다.

 

우선 ( 가 스택에 들어갈거고 들어가고 나면 우선순위가 0으로 가장 낮아진다.

6 출력

+ 는 ( 의 스택 내 우선순위 0보다 높으니까 스택에 넣고

5 출력 

* 의 우선순위 2는 +의 스택 내 우선순위 1보다 높으니까 스택에 넣고

( 여는 괄호는 스택 밖 우선순위가 가장 높으므로 스택에 넣고

2 출력

- 는 스택의 top이 ( 니까 항상 우선순위가 높으므로 스택에 넣고

8 출력

 

여기까지 계산하면 다음과 같다.

스택	출력
( + * ( -	6 5 2 8

 

이제 닫는 괄호 ')'가 나온다.

스택의 top 에 왼쪽 괄호 '('가 나올 때까지 스택에서 꺼내어 출력하고, 이때 '('는 출력하지 않고 버린다.

 

) 를 만났으니 - 를 출력하고 ( 는 버린다.

/ 가 나왔고 스택의 top은 * 이니까 우선순위가 2로 동일하다.

/ 보다 우선순위가 낮은 연산자를 만날 때까지 pop()하고 보다 낮을 경우 push()하는데 

*과 / 의 우선순위는 2로 동일하므로 * 을 pop한다.

+의 우선순위는 1, /의 우선순위는 2이므로 스택에 넣는다.  스택 상황  ==> ( + /

2를 출력

) 를 만났으니 /  +  를 출력하고 ( 는 버린다.

 

계산 결과이다.

스택	출력
	6 5 2 8 - * 2 / +

 

2. 후위표기법의 수식을 스택을 이용하여 계산한다.

6 5 2 8 - * 2 / +

1. 피연산자를 만나면 스택에 push 한다.

2. 연산자를 만나면 필요한 만큼 피연산자를 스택에서 Pop하여 연산하고, 결과를 다시 스택에 push한다.

3. 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

 

차례대로 보자.

6은 피연산자니까 스택에 넣는다.

5,2,8도 스택에 넣는다.

 

- 연산자를 만났으니 피연산자를 꺼내는데 이 때 순서는 8, 2 가 아닌 2, 8임에 주의하자.

2 - 8 = -6 계산결과를 스택에 넣는다.  스택상황 ==> 6 5 -6

 

* 연산자를 만났으니 피연산자 두 개를  꺼내 계산 후 스택에 넣는다.

5 * (-6) = -30  스택상황 ==> 6 -30

 

2를 만났으니 스택에 넣는다.

스택상황 ==> 6 -30 2

 

/ 를 만났으니 연산자 두 개를 꺼내 계산 후 스택에 넣는다.

(-30) / 2 = -15 스택상황 ==> 6 -15

 

+ 를 만났으니 연산자 두 개를 꺼내 계산 후 스택에 넣는다.

6 + (-15) 스택상황 ==> -9 

 

수식에 더 이상 토큰이 없으므로 스택에서 최종 결과값을 Pop하여 출력한다.

-9

 

파이썬 내장함수로 계산 eval()

문자열로 된 수식을 계산하며 올바른 수식이 아닐 경우 Syntax Error 예외가 발생한다.

수식은 <str> 문자열이어야 하고 기본적으로 실수 <float>를 반환한다는 점에 주의하자.

expression = "(6 + 5 * (2 - 8) / 2)"

print(eval(expression))
print(type(eval(expression)))

# -9.0
# <class 'float'>

 

 

 

참고자료

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

https://orkhanhuseyn.medium.com/what-are-stack-based-calculators-cf2dbe249264