题目：

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7" 3/2 " = 1" 3+5 / 2 " = 5

 

Note: Do not use the eval built-in library function.

链接： 

7/23/2017

6%...

很僵化的只会先infix to postfix，再来计算

注意：

1. string去掉white space: s.replaceAll("\\s+", "")

2. 各种类型的转换, String <--> Integer, String <--> Character...

3. Stack, Queue的接口函数，已经Queue的2套函数都要熟练

4. infix到postfix如何转换？运算数直接输出，运算符要跟stack最上面判断，如果stack top的优先级高或者有相同优先级，要把当前top的运算符输出。无论当前是否有更高的优先级，当前运算符必须要加到stack里面去，因为第二个运算数还没有处理到。最后要把最后一个运算数和所有stack里的运算符输出。

5. 运算postfix很简单，遇到运算数放到stack里，遇到运算符取出stack最上面2个运算数，将结果压回stack。最后stack中只剩下一个数，即为结果。

1 public class Solution { 2     public int calculate(String s) { 3         // remove white spaces from input string 4         s = s.replaceAll("\\s+",""); 5         Stack
     
       operators = new Stack<>(); 6         Queue
      
        postfix = new LinkedList<>(); 7          8         StringBuilder operand = new StringBuilder(); 9         for (int i = 0; i < s.length(); i++) {10             char c = s.charAt(i);11             // build operands from one or more characters12             if (c >= '0' && c <= '9') {13                 operand.append(c);14             } else {15                 // put last operand to output16                 postfix.offer(operand.toString());17                 operand = new StringBuilder();18                 // add operator to operators stack19                 if (!operators.isEmpty()) {20                     String prevOperator;21                     while (!operators.isEmpty()) {22                         prevOperator = operators.peek();23                         // if operator on top of stack has same or higher precedence, move top to output24                         if (prevOperator.equals("*") || prevOperator.equals("/") || c == '+' || c == '-') {25                             postfix.offer(operators.pop());26                         } else {27                             break;28                         }29                     }30                 }31                 // add current operator to operators stack, because the second operand is not visited yet32                 operators.push(Character.toString(c));33             }34         }35         // last operand not in postfix yet36         postfix.offer(operand.toString());37         // put all operators stack to postfix38         while (!operators.isEmpty()) {39             postfix.offer(operators.pop());40         }41         // calculate postfix42         Stack
       
         operandStack = new Stack<>();43         while (!postfix.isEmpty()) {44             String o = postfix.poll();45             if (o.equals("+") || o.equals("-") || o.equals("*") || o.equals("/")) {46                 Integer operand2 = operandStack.pop();47                 Integer operand1 = operandStack.pop();48                 Integer result;49                 if (o.equals("+")) {50                     result = operand1 + operand2;51                 } else if (o.equals("-")) {52                     result = operand1 - operand2;53                 } else if (o.equals("*")) {54                     result = operand1 * operand2;55                 } else {56                     result = operand1 / operand2;57                 }58                 operandStack.push(result);59             } else {60                 operandStack.push(Integer.valueOf(o));61             }62         }63         return operandStack.peek();64     }65 }
       
      
     

别人的答案

高优先级直接运算，低优先级存运算数

看不太懂，看解释会好一点

发现大家都是按照第一种做法来的，直接将中间值保存起来，这个都没有用到stack

将operand, operator放到2个不同的stack里

有详细解释

更多讨论