Jialong's Blog

Do things I love, and seek happiness.

0%

Dijkstra双栈——算术表达式求值

算数表达式

这里的算术表达式支持常见的二元运算符+-*/以及接受一个参数的平方根运算符sqrt。这里我们假定表达式中未省略所有的括号。

计算方法

  • 将操作数压入操作数栈
  • 将运算符压入运算符栈
  • 忽略左括号
  • 遇到右括号时,弹出一个运算符,弹出需要数量的操作数进行运算,然后将得到的结果再压入操作数栈。

代码实现

1
package edu.princeton.cs.algs4;
2
3
public class Evaluate {
4
	public static void main(String[] args)
5
	{
6
		Stack<String> ops = new Stack<String>();
7
		Stack<Double> vals = new Stack<Double>();
8
		while (!StdIn.isEmpty())
9
		{
10
			//读取字符,如果是运算符则压入运算符栈ops
11
			String s = StdIn.readString();
12
			if (s.equals("("));
13
			else if (s.equals("+"))    ops.push(s);
14
			else if (s.equals("-"))    ops.push(s);
15
			else if (s.equals("*"))    ops.push(s);
16
			else if (s.equals("/"))    ops.push(s);
17
			else if (s.equals("sqrt"))    ops.push(s);
18
			
19
			//如果字符为),则弹出运算符和操作数,计算结果并压入操作数栈vals
20
			else if (s.equals(")"))
21
			{
22
				String op = ops.pop();
23
				double v = vals.pop();
24
				if (op.equals("+"))    v = vals.pop() + v;
25
				else if (op.equals("-"))    v = vals.pop() - v;
26
				else if (op.equals("*"))    v = vals.pop() * v;
27
				else if (op.equals("/"))    v = vals.pop() / v;
28
				else if (op.equals("sqrt"))    v = Math.sqrt(v);
29
				
30
				vals.push(v);
31
			}
32
			//如果字符既非运算符又非括号,将其作为double值压入操作数栈vals
33
			else vals.push(Double.parseDouble(s));
34
		}
35
		StdOut.println(vals.pop());
36
	}
37
}