1 public class Solution {
2 enum TokenType { DIGIT, OP }
3
4 static class Token {
5 TokenType type;
6 int val;
7
8 public Token(int val, TokenType type) {
9 this.val = val;
10 this.type = type;
11 }
12 }
13
14 static final Token EOL = new Token(0, TokenType.OP);
15
16 static final Token[] TOKENS = new Token[256];
17
18 static {
19 TOKENS['+'] = new Token('+', TokenType.OP);
20 TOKENS['-'] = new Token('-', TokenType.OP);
21 TOKENS['*'] = new Token('*', TokenType.OP);
22 TOKENS['/'] = new Token('/', TokenType.OP);
23 TOKENS['('] = new Token('(', TokenType.OP);
24 TOKENS[')'] = new Token(')', TokenType.OP);
25 }
26
27 static class Tokenizer {
28
29 Scanner scanner;
30
31 Tokenizer(String s){
32 scanner = new Scanner(s);
33 scanner.useDelimiter("");
34 }
35
36 Token next(){
37 if(!scanner.hasNext()){
38 return EOL;
39 }
40
41 boolean num = false;
42 int buf = 0;
43 while (scanner.hasNextInt()){
44 num = true;
45 buf = buf * 10 + scanner.nextInt();
46 }
47
48 if(num){
49 return new Token(buf, TokenType.DIGIT);
50 }
51
52 char c = scanner.next().charAt(0);
53
54 if(TOKENS[c] != null){
55 return TOKENS[c];
56 }
57
58 return next();
59 }
60 }
61
62 static class RPNCalculator {
63 LinkedList<Integer> stack = new LinkedList<>();
64
65 void addToken(Token t){
66 if(t.type == TokenType.OP){
67
68 int v2 = stack.pop();
69 int v1 = stack.pop();
70
71 switch (t.val){
72 case '+':
73 stack.push(v1 + v2);
74 break;
75 case '-':
76 stack.push(v1 - v2);
77 break;
78 case '*':
79 stack.push(v1 * v2);
80 break;
81 case '/':
82 stack.push(v1 / v2);
83 break;
84 default:
85 // cant happen
86 }
87
88 } else { // DIGIT
89 stack.push(t.val);
90 }
91 }
92
93 int val(){
94 return stack.peek();
95 }
96 }
97
98 public int calculate(String s) {
99
100 RPNCalculator calculator = new RPNCalculator();
101
102 Tokenizer tokenizer = new Tokenizer(s);
103
104 LinkedList<Token> op = new LinkedList<>();
105
106 Token t;
107
108 next:
109 while ((t = tokenizer.next()) != EOL){
110
111 // convert to RPN
112
113 if(t.type == TokenType.DIGIT){
114 calculator.addToken(t);
115
116 } else { // type == OP
117
118 retry:
119 while(true) {
120
121 if(op.isEmpty()){
122 op.push(t);
123 continue next;
124 }
125
126 Token top = op.peek();
127
128 switch (t.val) {
129 case '(':
130 op.push(t);
131 break;
132
133 case '+':
134 case '-':
135 if (top.val == '+' || top.val == '-' ||
136 top.val == '*' || top.val == '/') {
137
138 calculator.addToken(op.pop());
139 continue retry;
140 }
141
142 op.push(t);
143
144 break;
145
146 case '*':
147 case '/':
148 if (top.val == '*' || top.val == '/') {
149 calculator.addToken(op.pop());
150 continue retry;
151 }
152
153 op.push(t);
154
155 break;
156
157 case ')':
158
159 while (!op.isEmpty()) {
160 top = op.pop();
161
162 if (top.val == '(') continue next;
163
164 calculator.addToken(top);
165 }
166
167 default:
168 // cant happen
169 }
170
171 continue next;
172 }
173 }
174 }
175
176 while (!op.isEmpty()){
177 calculator.addToken(op.pop());
178 }
179
180 return calculator.val();
181 }
182
183 }