LeetCode - Algorithms - 227. Basic Calculator II

这题是关于表达式解析的，2007年学习数据结构曾经实现过，思路是把中缀表达式转换为后缀表达式，再结合栈这种数据结构计算后缀表达式，就拿来执行下，结果LeetCode test case 1*2-3/4+5*6-7*8+9/10 报了个错 java.lang.ArithmeticException: / by zero，用StringTokenizer把操作符与操作数拆开，改了下原来的代码，最终运行通过了，但自己对其中的机理还是有点知其然而不知其所以然。

原来java7以后可以在switch的case语句里用String类型。

Strings in switch Statements

In the JDK 7 release, you can use a String object in the expression of a switch statement.

Basic Calculator这系列的题看来也是比较经典的，表达式解析好像是数据结构与编译原理的交叉点之一。

Java

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

class Solution {
	public int postfixCalculator(List<String> postfixExpr) {
		Stack<Integer> stk = new Stack<Integer>();
		for (int i = 0; i < postfixExpr.size(); i++) {
			String s = postfixExpr.get(i);
			int a, b, x;
			switch (s) {
			case "*":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = a * b;
					stk.push(new Integer(x));
				}
				break;
			case "+":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = a + b;
					stk.push(new Integer(x));
				}
				break;
			case "-":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = b - a;
					stk.push(new Integer(x));
				}
				break;
			case "/":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = b / a;
					stk.push(new Integer(x));
				}
				break;
			default:
				stk.push(new Integer(s));
				break;
			}
		}
		int ret = 0;
		if (!stk.isEmpty())
			ret = stk.pop().intValue();
		return ret;
	}

	public List<String> infix2postfix(String infixExpr) {
		List<String> r = new ArrayList<String>();
		Stack<String> stk = new Stack<String>();
		List<String> list = new ArrayList<String>();
		StringTokenizer st = new StringTokenizer(infixExpr,"[\\+\\-\\*/()]",true);
	     while (st.hasMoreTokens()) {
	         list.add(st.nextToken());
	     }
		for (int i = 0; i < list.size(); i++) {
			String s = list.get(i);
			switch (s) {
			case "*":
			case "/":
				while (!stk.isEmpty() && (stk.peek().equals("*") || stk.peek().equals("/"))) {
					r.add( stk.pop() );
				}
				stk.push(s);
				break;
			case "+":
			case "-":
				while (!stk.isEmpty() && !stk.peek().equals("(")) {
					r.add( stk.pop() );
				}
				stk.push(s);
				break;
			case "(":
				stk.push(s);
				break;
			case ")":
				while (!stk.isEmpty() && !stk.peek().equals("(")) {
					r.add(stk.pop());
				}
				if (stk.peek().equals("("))
					stk.pop();
				break;
			default:
				r.add(s);
			}
		}

		while (stk != null && !stk.isEmpty()) {
			r.add( stk.pop() );
		}

		return r;
	}    

    public int calculate(String s) {
        return postfixCalculator(infix2postfix(s.replaceAll(" ", "")));
    }
}

Submission Detail

  • 109 / 109 test cases passed.
  • Runtime: 98 ms
  • Your runtime beats 5.79 % of java submissions.