使用Java自身的输入输出库实现Dijkstra的双栈算术表达式求值算法
一、算法原理
计算表达式( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
分析书上有，不赘述。算法如下：
1
2
3
4
| 将操作数压入操作数栈；
将运算符压入运算符栈；
忽略左括号；
在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。
|
书上源码：
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
| import java.util.Stack;
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);
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
|
二、问题
算法第四版中的Dijkstra的双栈算术表达式求值算法中，while (!StdIn.isEmpty()) 循环无法跳出
StdIn.isEmpty()的实现:
1
2
3
| public static boolean isEmpty() {
return !scanner.hasNext();
}
|
三、解决方法
法一｜敌动我不动：
控制台输入以下快捷键：
macOS ： Command+D
Windows ： Ctrl+D
原理：⌘D组合键可让您发送EOF(文件末尾)，即表示无法从数据源读取更多数据。
法二｜敌不动我动：
不用StdIn，使用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
| import java.util.Scanner;
import java.util.Stack;
public class MyEvaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
Scanner sc = new Scanner(System.in);
String str;
System.out.println("请输入算术表达式，中间用空格隔开，括号用英文字符：");
str = sc.nextLine();
String[] sArray = str.split(" ");
for (String s : sArray) {
if (s.equals("(")) ;
else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) ops.push(s);
else if (s.equals(")")) {
String op = ops.pop();
double val = vals.pop();
if (op.equals("+")) val = vals.pop() + val;
else if (op.equals("-")) val = vals.pop() - val;
else if (op.equals("*")) val = vals.pop() * val;
else if (op.equals("/")) val = vals.pop() / val;
vals.push(val);
} else vals.push(Double.parseDouble(s));
}
System.out.println(str + " = " + vals.pop());
}
}
|
运算示例：
循环输入版本：
如果要循环计算算术表达式：
- 请在合适位置添加
while(sc.hasNextLine())
- 除去提示语句，因为会造成输出上逻辑混乱，但是代码本身是可以执行的
- 设置退出条件，否则程序循环执行，就跟书上的一样了。
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
| import java.util.Scanner;
import java.util.Stack;
public class MyEvaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
Scanner sc = new Scanner(System.in);
String str;
while (sc.hasNextLine()) {
str = sc.nextLine();
if (str.equals("q")) {
System.out.println("已退出，终止程序！");
break;
}
String[] sArray = str.split(" ");
for (String s : sArray) {
if (s.equals("(")) ;
else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) ops.push(s);
else if (s.equals(")")) {
String op = ops.pop();
double val = vals.pop();
if (op.equals("+")) val = vals.pop() + val;
else if (op.equals("-")) val = vals.pop() - val;
else if (op.equals("*")) val = vals.pop() * val;
else if (op.equals("/")) val = vals.pop() / val;
vals.push(val);
} else vals.push(Double.parseDouble(s));
}
System.out.println(str + " = " + vals.pop());
}
}
}
|
示例：
附录
参考：
- Dijkstra的双栈算术表达式求值算法 Java实现 问题：char型，只能处理个位数
- java - 如何使StdIn.isEmpty()返回true？