Dequeue로 계산기 만들기

package com.lgcns.test.calculator;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * Calculator (30분 ~ 40분)
 *
 * 사칙연산 계산기 만들기
 * 1*8+3+6+5/2*5-9 와 같이 사칙연산의 답을 구하는 문제
 *
 * *, /은 +, -보다 우선순위가 높다.
 * 각 숫자는 한자리 자연수로 이루어지고 
 * 나누셈의 경우 소수점은 버리고(5/2=2)
 * 0으로 나누는 경우는 없다고 가정한다.
 *
 * -----------
 * Pseudocode
 * -----------
 * String 을 분해해서 1번 Deque 에 담는다. (순서를 보존해야 한다.)
 * 보조 2번 Deque을 하나 준비한다.
 *
 * 1번 Deque에 대해 * / 연산을 수행한다.
 * 연산은 항상 숫자 연산자 숫자 로 이루어 지므로 3개씩 꺼낸다.

 * 1번 Deque이 1만 남을때 까지 looping {
 * 3개를 꺼낸다. (pop)
 * 2번째가 * 이거나 / 면 연산을 수행하고 다시 Deque 에 담는다. (push)
 *  2번째가 * /이 아니라면 2번째 Deque 1,2를 담고 (add) 3은 Deque1에 담는다. (push)
 * }
 *
 * 2번 Deque이 1만 남으때 까지 looping {
 * 3개를 꺼낸다.
 * 2번째가 + 이거나 -면  연산을 수행하고 다시 Deque 에 담는다.
 * }
 *
 * 
 */
public class Calculator {

int calculate(String str) {
Deque deque1 = build(str);
Deque queue2 = new ArrayDeque();
while (deque1.size() > 1) {
String operand1 = deque1.pop();
String operator = deque1.pop();
String operand2 = deque1.pop();
if ("*".equals(operator)) {
int i1 = Integer.parseInt(operand1);
int i2 = Integer.parseInt(operand2);
int r = i1 * i2;
deque1.push(String.valueOf(r));
} else if ("/".equals(operator)) {
int i1 = Integer.parseInt(operand1);
int i2 = Integer.parseInt(operand2);
int r = i1 / i2;
deque1.push(String.valueOf(r));
} else {
queue2.add(operand1);
queue2.add(operator);
deque1.push(operand2);
}
}

queue2.add(deque1.pop());

while (queue2.size() > 1) {
String operand1 = queue2.pop();
String operator = queue2.pop();
String operand2 = queue2.pop();
if ("+".equals(operator)) {
int i1 = Integer.parseInt(operand1);
int i2 = Integer.parseInt(operand2);
int r = i1 + i2;
queue2.push(String.valueOf(r));
} else if ("-".equals(operator)) {
int i1 = Integer.parseInt(operand1);
int i2 = Integer.parseInt(operand2);
int r = i1 - i2;
queue2.push(String.valueOf(r));
} else {
System.out.println("=");
}
}

return Integer.parseInt(queue2.pop());
}

public Deque build(String str) {
StringTokenizer st = new StringTokenizer(str, "*/-+", true);
Deque queue = new ArrayDeque();
while (st.hasMoreTokens()) {
queue.add(st.nextToken());
}
return queue;
}

public static void main(String[] args) {
Calculator calculator = new Calculator();
System.out.println(calculator.calculate("1*8/2+6+5/2*5-9")); // 18
System.out.println(calculator.calculate("1*8-3-6+5/2*6-9")); // 2
}

}