LeetCode - Algorithms - 224. Basic Calculator

Java

1

代码见前一篇

Submission Detail

  • 37 / 37 test cases passed.
  • Runtime: 143 ms
  • Your runtime beats 6.05 % of java submissions.

2 Shunting-yard algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.StringTokenizer;

class Solution {
    public int calculate(String s) {
        return evalRPN(infixToPostfix(s.replaceAll(" ","")));      
    }
    
    private int evalRPN(List<String> exprlist){
        LinkedList<Integer> stack = new LinkedList<Integer>();

        for (String token : exprlist) {
            Integer tokenNum = null;
            try{
                tokenNum = Integer.parseInt(token);
            }catch(NumberFormatException e){}
            if(tokenNum != null){
                stack.push(Integer.parseInt(token+""));
            }else if(token.equals("-")){
                int secondOperand = stack.pop();
                int firstOperand = stack.pop();
                stack.push(firstOperand - secondOperand);
            }else if(token.equals("+")){
                int secondOperand = stack.pop();
                int firstOperand = stack.pop();
                stack.push(firstOperand + secondOperand);
            }else{
                return 0;
            }
        }
        int r = stack.pop();
        return r;
    }    
    
    private List<String> infixToPostfix(String infix) {
        List<String> list = new ArrayList<String>();
        final String ops = "-+";

        Stack<Integer> stack = new Stack<Integer>();

        StringTokenizer st = new StringTokenizer(infix,"[\\+\\-()]",true);
        while (st.hasMoreTokens()) {
            String token = st.nextToken();
            if (token.isEmpty())
                continue;
            char c = token.charAt(0);
            int idx = ops.indexOf(c);

            if (idx != -1) {
                if (stack.isEmpty())
                    stack.push(idx);

                else {
                    while (!stack.isEmpty()) {
                        int prec2 = stack.peek() / 2;
                        int prec1 = idx / 2;
                        if (prec2 > prec1 || prec2 == prec1)
                            list.add( ops.charAt(stack.pop()) + "" );
                        else break;
                    }
                    stack.push(idx);
                }
            }
            else if (c == '(') {
                stack.push(-2);
            }
            else if (c == ')') {
                while (stack.peek() != -2)
                    list.add( ops.charAt(stack.pop())+"" );
                stack.pop();
            }
            else {
                list.add( token );
            }
        }
        while (!stack.isEmpty())
            list.add( ops.charAt(stack.pop())+"" );
        return list;
    }    
}

Submission Detail

  • 37 / 37 test cases passed.
  • Runtime: 172 ms, faster than 7.80% of Java online submissions for Basic Calculator.
  • Memory Usage: 55.4 MB, less than 20.00% of Java online submissions for Basic Calculator.

Resources