一小时搞定关于栈的那点事儿，其实挺简单的( 二 ) _栈

文章插图
6 双栈运算这部分来自《算法（第四版）》，我觉得实在是相当不错，就放在这里了，算是张涨姿势吧
计算算式 `` 的值，我们使用两个栈来完成这个任务，一个栈用来保存运算符，一个栈用来保存操作数。
表达式由括号、运算符和操作数组成。我们根据以下4种情况从左到右逐个将这些实体送入栈处理：

将操作数压入操作数栈
将运算符压入运算符栈
忽略左括号
在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈

package com.banana.stack;
import JAVA.util.Stack;
public class Evaluate {
public static void main(String[] args) {
String str = "(1 + ( (2+3) * (4*5) ) )";
System.out.println(calculate(str));
}
public static double calculate(String str) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
for (int i = 0; i < str.length(); i++) {
String ele = "" + str.charAt(i);
// Neglect the operator "(" and " "
if (ele.equals("(") || ele.equals(" ")) ;
else if (ele.equals("+")) ops.push(ele);
else if (ele.equals("-")) ops.push(ele);
else if (ele.equals("*")) ops.push(ele);
else if (ele.equals("/")) ops.push(ele);
else if (ele.equals(")")) {
String op = ops.pop();
double v1 = vals.pop();
double v2 = vals.pop();
if (op.equals("+")) vals.push(v1 + v2);
if (op.equals("-")) vals.push(v1 - v2);
if (op.equals("*")) vals.push(v1 * v2);
if (op.equals("/")) vals.push(v1 / v2);
} else vals.push(Double.valueOf(ele));
}
return vals.pop();
}
}
这段Stack的用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到结果。有了泛型，我们只需实现Stack一次即可使用String值得栈和Double值得栈。