Vla*_* K. 1 java algorithm stack
我正在读一本关于算法和数据结构的书，并尝试遵循其中的示例。我尝试实现的是 Dijkstra 的用于表达式求值的两栈算法。它以字符串形式输入( 1 + 2 ) * 3，然后计算表达式。我的代码可以编译，但不会产生正确的输出。
上述表达式的输出是：
3.0
这是我的代码：
public class Eval {
public static void main(String[] args) {
String s = "( 1 + 2 ) * 3";
evaluateAndPrintResult(s);
}
public static void evaluateAndPrintResult(String s)
{
String[] str = s.split("\\s+");
Queue<String> q = new LinkedList<String>();
for(String ss : str)
q.add(ss);
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!q.isEmpty())
{ // Read token, push if operator.
String token = q.poll();
if (token.equals("(")) ;
else if (token.equals("+")) ops.push(s);
else if (token.equals("-")) ops.push(s);
else if (token.equals("*")) ops.push(s);
else if (token.equals("/")) ops.push(s);
else if (token.equals("sqrt")) ops.push(s);
else if (token.equals(")"))
{ // Pop, evaluate, and push result if token is ")".
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);
} // Token not operator or paren: push double value.
else vals.push(Double.parseDouble(token));
}
System.out.println(vals.pop());
}
}
我不太了解该程序，无法纠正它。我该如何修正我的程序？
您的问题出在您使用的几个地方ops.push(s)。你应该使用ops.push(token).
您正在推送整个表达式，您应该只推送当前标记。
此代码正确打印9.0。
public static void evaluateAndPrintResult(String s) {
String[] str = s.split("\\s+");
Queue<String> q = new LinkedList<>();
q.addAll(Arrays.asList(str));
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
while (!q.isEmpty()) { // Read token, push if operator.
String token = q.poll();
if (token.equals("(")) {
} else if (token.equals("+")) {
ops.push(token);
} else if (token.equals("-")) {
ops.push(token);
} else if (token.equals("*")) {
ops.push(token);
} else if (token.equals("/")) {
ops.push(token);
} else if (token.equals("sqrt")) {
ops.push(token);
} else if (token.equals(")")) { // Pop, evaluate, and push result if token is ")".
// Replace the top exp with it' result.
double v = vals.pop();
String op = ops.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);
} else {
// Token not operator or paren: push double value.
vals.push(Double.parseDouble(token));
}
}
System.out.println(vals.pop());
}
public void test() {
evaluateAndPrintResult("( ( 1 + 2 ) * 3 )");
}
但是，该表达式的"( 1 + 2 ) * 3"计算结果仍然为3.0。要解决这个问题，您需要评估您推送的最后一个操作（如果有）。
public static void evaluateAndPrintResult(String s) {
String[] str = s.split("\\s+");
Queue<String> q = new LinkedList<>();
q.addAll(Arrays.asList(str));
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
while (!q.isEmpty()) { // Read token, push if operator.
String token = q.poll();
if (token.equals("(")) {
} else if (token.equals("+")) {
ops.push(token);
} else if (token.equals("-")) {
ops.push(token);
} else if (token.equals("*")) {
ops.push(token);
} else if (token.equals("/")) {
ops.push(token);
} else if (token.equals("sqrt")) {
ops.push(token);
} else if (token.equals(")")) {
vals.push(evaluateOp(ops, vals));
} else {
// Token not operator or paren: push double value.
vals.push(Double.parseDouble(token));
}
}
System.out.println(evaluateOp(ops, vals));
}
private static Double evaluateOp(Stack<String> ops, Stack<Double> vals) {
// Replace the top exp with its result.
double v = vals.pop();
String op = ops.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);
}
return v;
}
public void test() {
evaluateAndPrintResult("( 1 + 2 ) * 3");
}
最后 - 一种更简洁的方法。
public static void evaluateAndPrintResult(String s) {
String[] str = s.split("\\s+");
Queue<String> q = new LinkedList<>();
q.addAll(Arrays.asList(str));
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
while (!q.isEmpty()) { // Read token, push if operator.
String token = q.poll();
switch (token) {
case "(":
break;
case "+":
case "-":
case "*":
case "/":
case "sqrt":
ops.push(token);
break;
case ")":
vals.push(evaluateOp(ops, vals));
break;
default:
// Token not operator or paren: push double value.
vals.push(Double.parseDouble(token));
break;
}
}
System.out.println(s + " = " + evaluateOp(ops, vals));
}
private static Double evaluateOp(Stack<String> ops, Stack<Double> vals) {
// Replace the top exp with its result.
double v = vals.pop();
if (!ops.empty()) {
String op = ops.pop();
switch (op) {
case "+":
v = vals.pop() + v;
break;
case "-":
v = vals.pop() - v;
break;
case "*":
v = vals.pop() * v;
break;
case "/":
v = vals.pop() / v;
break;
case "sqrt":
v = Math.sqrt(v);
break;
default:
break;
}
}
return v;
}
public void test() {
evaluateAndPrintResult("( ( 1 + 2 ) * 3 )");
}