在算法书上看到了Dijkstra的表达式求值算法，不断地将括号包围的子表达式替换为一个数值，最终就可以求得结果。相比于转换成后缀表达式的算法，该算法很简洁，但限制却十分地大：必须将所有 expr op expr 用括号括起来，如：( 1 + ( ( 2 + 3 ) + ( 4 * 5 ) ) )。
Dijkstra算法（PS：下面的实现中，每次读到的字符串s是一个一个的元素数字or运算符）：
public class Evaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!StdIn.isEmpty()) { // 读取字符，如果是运算符则压入栈
String s = StdIn.readString();
if (s.equals("(")) ;
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")")) { // 如果字符为 ")"，弹出运算符和操作数，计算结果并压入栈
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("*")) v = vals.pop() * v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
} // 如果字符既非运算符也不是括号，将它作为 double 值压入栈
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
然后我就尝试改进算法，去除必须添加括号限制，思路也是将括号围起来的子表达式求值然后替换，相对来看，改进后的算法代码行数增加了25行左右（去除栈定义、数字识别的代码），但依然要比转换成后缀表达式要简单、容易很多
如：-1 + 2 * (3 * 3 - 10) => -1 + 2 * (-1) => -3
/////// stack begin /////////
type stack []interface{}
func (s stack) empty() bool {
return len(s) == 0
}
func (s *stack) push(e interface{}) {
*s = append(*s, e)
}
func (s *stack) pop() interface{} {
lastIdx := len(*s) - 1
e := (*s)[lastIdx]
*s = (*s)[:lastIdx]
return e
}
/////// stack end /////////
func Calculate(expr string) int {
numStack, opStack, curSubexprNumCount := stack{}, stack{}, stack{}
expr = "(" + expr + ")"
for i := 0; i < len(expr); i++ {
ch := expr[i]
switch ch {
case '(':
if !curSubexprNumCount.empty() { // 遇到下一个子表达式，则当前表达式数字个数加一
curSubexprNumCount.push(curSubexprNumCount.pop().(int) + 1)
}
curSubexprNumCount.push(0)
opStack.push(ch)
case '+', '-', '*', '/':
opStack.push(ch)
case ')':
numStk, opStk := stack{}, stack{} // 正序化
numCount := curSubexprNumCount.pop().(int)
for j := 0; j < numCount; j++ {
numStk.push(numStack.pop())
}
for op := opStack.pop().(byte); op != '('; op = opStack.pop().(byte) {
opStk.push(op)
}
if len(numStk) == len(opStk) { // + 或 - 开头的子表达式：-1+2...
if op := opStk.pop().(byte); op == '-' {
numStk.push(-numStk.pop().(int))
}
}
var tmp stack
tmp.push(numStk.pop().(int))
for !opStk.empty() {
x := numStk.pop().(int)
switch opStk.pop().(byte) {
case '+': tmp.push(x)
case '-': tmp.push(-x)
case '*': tmp.push(tmp.pop().(int) * x)
case '/': tmp.push(tmp.pop().(int) / x)
}
}
result := 0
for !tmp.empty() {
result += tmp.pop().(int)
}
numStack.push(result) // 将求得的子表达式值放入栈中
default:
if !unicode.IsDigit(rune(ch)) {
continue
}
num := 0
for ; i < len(expr) && unicode.IsDigit(rune(expr[i])); i++ {
num = 10 * num + int(expr[i]) - '0'
}
i-- // 退一步
numStack.push(num)
curSubexprNumCount.push(curSubexprNumCount.pop().(int) + 1)
}
}
result := 0
for !numStack.empty() {
result += numStack.pop().(int)
}
return result
}