LeetCode solutions by tgic

Basic Calculator

https://leetcode.com/problems/basic-calculator

Last Update 2015-06-28 16:20:02 +0000 View on Github

Source code Read on Github

  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 }
comments powered by Disqus

LeetCode solutions by tgic

  • LeetCode solutions by tgic
  • [email protected]
  • Creative Commons License
    This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
  • tg123
  • tg123/leetcode

LeetCode java solutions by tgic