227. Basic Calculator II

题目：

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.

链接： http://leetcode.com/problems/basic-calculator-ii/

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<String> operators = new Stack<>();
 6         Queue<String> 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 characters
12             if (c >= '0' && c <= '9') {
13                 operand.append(c);
14             } else {
15                 // put last operand to output
16                 postfix.offer(operand.toString());
17                 operand = new StringBuilder();
18                 // add operator to operators stack
19                 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 output
24                         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 yet
32                 operators.push(Character.toString(c));
33             }
34         }
35         // last operand not in postfix yet
36         postfix.offer(operand.toString());
37         // put all operators stack to postfix
38         while (!operators.isEmpty()) {
39             postfix.offer(operators.pop());
40         }
41         // calculate postfix
42         Stack<Integer> 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 }

别人的答案

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

https://discuss.leetcode.com/topic/16935/share-my-java-solution

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

https://discuss.leetcode.com/topic/16807/17-lines-c-easy-20-ms

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

https://discuss.leetcode.com/topic/17435/java-straight-forward-iteration-solution-with-comments-no-stack-o-n-o-1

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

https://discuss.leetcode.com/topic/17213/my-28ms-c-code-with-two-stacks-one-for-op-one-for-oprand-extension-to-cover-also-given

有详细解释

https://discuss.leetcode.com/topic/41118/simple-c-solution-beats-85-submissions-with-detailed-explanations