계산기

SimpleCalc.java - 예제의 원본 출처를 알 수 없습니다. -_-;

큐(queue),스택(stack) 을 이용해서 괄호'(' 까지 있는 산식을 계산해 보자.

queue : 먼저 입력된 값을 먼저 반환

stack : 마지막으로 입력된 값을 먼저 반환

사용

queue : 계산식의 숫자, operator

statck : operator, 계산된 값, 계산할 값

계산식 문자열을 왼쪽에서 부터 읽어서 숫자면 queue에 operator 라면 statck에 담는다.

새로운 operator를 stack에 담을 때, stack에 이미 있는 operator 의 우선순의가 같거나 높으면 stack의 operator를 queue로 옮긴 후 새로운 operator를 stack에 담는다.

1. queue엔 모든 숫자, operator가 있고, stack은 비워진 상태임.
2. queue에서 하나씩 꺼내 statck에 담고, queue에서 꺼내진 것이 operator라면 stack에서 2개의 수를 꺼내 해당 operator로 계산하고, 결과값을 stack에 담는다.
3. queue가 비워졌을 때 stack에 남은 값이 계산식의 결과값임.

로직설명

1. 1 + 2

		queue	stack
1	1 을 queue에 담는다	1
2	+ 를 stack에 담는다	1	+
3	2 를 queue에 담는다	1 2	+
4	stack에 담긴 + 를 꺼내서 queue에 담는다	1 2 +
5	queue에서 먼저 입력된 것부터 꺼내서 stack에 담는다. 하나씩 꺼내 stack에 담다가 operator가 나오면 stack에 담겨진 두 수를 꺼내 해당 operator로 계산한다. 계산 결과를 stack에 담는다.	2 + +	1 1 2 3

1. 1 + 2 * 3

		queue	stack
1	1 을 queue에 담는다	1
2	+ 를 stack에 담는다	1	+
3	2 를 queue에 담는다.	1 2	+
4	* 를 stack에 담는다.(+ 는 * 보다 우선순위가 낮다)	1 2	+ *
5	3 을 queue에 담는다	1 2 3	+ *
6	stack에 담긴 *,+를 queue에 담는다	1 2 3 * +
7	queue에서 하나씩 꺼내 stack에 담는다. operator를 만나면 stack에서 2개를 꺼내 계산 후 결과값을 stack에 담는다 queue에서 operator "*" 가 나왔기 때문에 stack에서 2, 3를 꺼내 해당 operator로 계산하고, 결과값 6을 stack에 담는다	* + +	1 2 3 1 6
8	queue에서 operator "+" 가 나왔기 때문에 stack에서 1, 6을 꺼내 해당 opreator로 계산하고, 결과값 7을 stack에 담는다		7

1. (1 + 2) * 3

		queue	stack
1	( 를 stack에 담는다		(
2	1 을 queue에 담는다	1	(
3	+ 를 statck에 담는다. "(" 의 경우 ")"를 만날때까지 꺼내지 않음.	1	( +
4	2 를 queue에 담는다	1 2	( +
5	) 를 만나면 stack에서 "(" 전까지를 queue에 담고, "(" 는 버린다	1 2 +
6	* 를 stack에 담는다	1 2 +	*
7	3 을 queue에 담는다	1 2 + 3	*
8	stack에 담긴 "*"를 queue에 담는다	1 2 + 3 *
9	queue에서 하나씩 꺼내 stack에 담는다. queue에서 operator가 나왔다면 stack에서 두개를 꺼내 해당 operator로 계산하고, 결과값을 stack에 담는다	3 *	3 9

이 글은 스프링노트에서 작성되었습니다.