压栈思想计算Java运算表达式

傷城~ 2022-06-13 00:29 68阅读 0赞

###     ###

栈的规则是先进后出。利用压栈的思想来计算四则运算表达式是这样的：我们给定两个栈，一个用来存放数字、一个用来存放对应的操作符。假定我们有一个给定的四则运算表达式a+b+c/d\*(e+f)-d\*a，那我们先把这个表达式拆分成一个个的数字或者是运算符、或者就是括号了。然后我们从左至右遍历每一个元素，遍历过程中遵循步骤和原则如下：

（1）遇到数字则直接压到数字栈顶。

（2）遇到运算符（+-\*/）时，若操作符栈为空，则直接放到操作符栈顶，否则，见（3）。

（3）若操作符栈顶元素的优先级比当前运算符的优先级小，则直接压入栈顶，否则执行步骤（4）。

（4）弹出数字栈顶的两个数字并弹出操作符栈顶的运算符进行运算，把运算结果压入数字栈顶，重复（2）和（3）直到当前运算符被压入操作符栈顶。

（5）遇到左括号“（”时则直接压入操作符栈顶。

（6）遇到右括号“）”时则依次弹出操作符栈顶的运算符运算数字栈的最顶上两个数字，直到弹出的操作符为左括号。

下面的例子中分别使用java.util.Vector和java.util.Stack基于上述原则实现了这一运算过程。

Java代码   ![收藏代码][icon_star.png]

1.  import java.util.HashMap;  
2.  import java.util.Map;  
3.  import java.util.Stack;  
4.  import java.util.StringTokenizer;  
5.  import java.util.Vector;  
6.  import java.util.regex.Pattern;  
7.    
8.  public class Test \{  
9.    
10.     public static void main(String args\[\]) \{  
11.         String computeExpr = "1 + 5 \* 6 + 3 \* (2 + 3\*2+2-1+3\*3) + 10/5 - 6\*1";  
12.         Test test = new Test();  
13.         double result1 = test.computeWithVector(computeExpr);  
14.         double result2 = test.computeWithStack(computeExpr);  
15.         System.out.println(result1 + "=======" + result2);  
16.     \}  
17.   
18.     /\*\* 
19.      \* 利用java.util.Vector计算四则运算字符串表达式的值，如果抛出异常，则说明表达式有误，这里就没有控制 
20.      \* @param computeExpr 四则运算字符串表达式 
21.      \* @return 计算结果 
22.      \*/  
23.     public double computeWithVector(String computeExpr) \{  
24.         StringTokenizer tokenizer = new StringTokenizer(computeExpr, "+-\*/()", true);  
25.         Vector<Double> nums = new Vector<Double>();  
26.         Vector<Operator> operators = new Vector<Operator>();  
27.         Map<String, Operator> computeOper = this.getComputeOper();  
28.         Operator curOper;  
29.         String currentEle;  
30.         while (tokenizer.hasMoreTokens()) \{  
31.             currentEle = tokenizer.nextToken().trim();  
32.             if (!"".equals(currentEle)) \{ //只处理非空字符  
33.                 if (this.isNum(currentEle)) \{ // 数字  
34.                     nums.add(Double.valueOf(currentEle));  
35.                 \} else \{ // 非数字，即括号或者操作符  
36.                     curOper = computeOper.get(currentEle);  
37.                     if (curOper != null) \{ // 是运算符  
38.                         // 运算列表不为空且之前的运算符优先级较高则先计算之前的优先级  
39.                         while (!operators.isEmpty()  
40.                                 && operators.lastElement().priority() >= curOper  
41.                                         .priority()) \{  
42.                             compute(nums, operators);  
43.                         \}  
44.                         // 把当前运算符放在运算符队列的末端  
45.                         operators.add(curOper);  
46.                     \} else \{ // 括号  
47.                         if ("(".equals(currentEle)) \{ // 左括号时直接放入操作列表中  
48.                             operators.add(Operator.BRACKETS);  
49.                         \} else \{ // 当是右括号的时候就把括号里面的内容执行了。  
50.                             // 循环执行括号里面的内容直到遇到左括号为止。试想这种情况(2+5\*2)  
51.                             while (!operators.lastElement().equals(Operator.BRACKETS)) \{  
52.                                 compute(nums, operators);  
53.                             \}  
54.                             //移除左括号  
55.                             operators.remove(operators.size()-1);  
56.                         \}  
57.                     \}  
58.                 \}  
59.             \}  
60.         \}  
61.         // 经过上面代码的遍历后最后的应该是nums里面剩两个数或三个数，operators里面剩一个或两个运算操作符  
62.         while (!operators.isEmpty()) \{  
63.             compute(nums, operators);  
64.         \}  
65.         return nums.firstElement();  
66.     \}  
67.       
68.     /\*\* 
69.      \* 利用java.util.Stack计算四则运算字符串表达式的值，如果抛出异常，则说明表达式有误，这里就没有控制 
70.      \* java.util.Stack其实也是继承自java.util.Vector的。 
71.      \* @param computeExpr 四则运算字符串表达式 
72.      \* @return 计算结果 
73.      \*/  
74.     public double computeWithStack(String computeExpr) \{  
75.         //把表达式用运算符、括号分割成一段一段的，并且分割后的结果包含分隔符  
76.         StringTokenizer tokenizer = new StringTokenizer(computeExpr, "+-\*/()", true);  
77.         Stack<Double> numStack = new Stack<Double>();   //用来存放数字的栈  
78.         Stack<Operator> operStack = new Stack<Operator>();  //存放操作符的栈  
79.         Map<String, Operator> computeOper = this.getComputeOper();    //获取运算操作符  
80.         String currentEle;  //当前元素  
81.         while (tokenizer.hasMoreTokens()) \{  
82.             currentEle = tokenizer.nextToken().trim();  //去掉前后的空格  
83.             if (!"".equals(currentEle)) \{   //只处理非空字符  
84.                 if (this.isNum(currentEle)) \{ //为数字时则加入到数字栈中  
85.                     numStack.push(Double.valueOf(currentEle));  
86.                 \} else \{ //操作符  
87.                     Operator currentOper = computeOper.get(currentEle);//获取当前运算操作符  
88.                     if (currentOper != null) \{  //不为空时则为运算操作符  
89.                         while (!operStack.empty() && operStack.peek().priority() >= currentOper.priority()) \{  
90.                             compute(numStack, operStack);  
91.                         \}  
92.                         //计算完后把当前操作符加入到操作栈中  
93.                         operStack.push(currentOper);  
94.                     \} else \{ //括号  
95.                         if ("(".equals(currentEle)) \{ //左括号时加入括号操作符到栈顶  
96.                             operStack.push(Operator.BRACKETS);  
97.                         \} else \{ //右括号时, 把左括号跟右括号之间剩余的运算符都执行了。  
98.                             while (!operStack.peek().equals(Operator.BRACKETS)) \{  
99.                                 compute(numStack, operStack);  
100.                             \}  
101.                             operStack.pop();//移除栈顶的左括号  
102.                         \}  
103.                     \}  
104.                 \}  
105.             \}  
106.         \}  
107.         // 经过上面代码的遍历后最后的应该是nums里面剩两个数或三个数，operators里面剩一个或两个运算操作符  
108.         while (!operStack.empty()) \{  
109.             compute(numStack, operStack);  
110.         \}  
111.         return numStack.pop();  
112.     \}  
113.       
114.     /\*\* 
115.      \* 判断一个字符串是否是数字类型 
116.      \* @param str 
117.      \* @return 
118.      \*/  
119.     private boolean isNum(String str) \{  
120.         String numRegex = "^\\\\d+(\\\\.\\\\d+)?$";   //数字的正则表达式  
121.         return Pattern.matches(numRegex, str);  
122.     \}  
123.       
124.     /\*\* 
125.      \* 获取运算操作符 
126.      \* @return 
127.      \*/  
128.     private Map<String, Operator> getComputeOper() \{  
129.         return new HashMap<String, Operator>() \{ // 运算符  
130.             private static final long serialVersionUID = 7706718608122369958L;  
131.             \{  
132.                 put("+", Operator.PLUS);  
133.                 put("-", Operator.MINUS);  
134.                 put("\*", Operator.MULTIPLY);  
135.                 put("/", Operator.DIVIDE);  
136.             \}  
137.         \};  
138.     \}  
139.   
140.     /\*\* 
141.      \* 取nums的最后两个数字，operators的最后一个运算符进行运算，然后把运算结果再放到nums列表的末端 
142.      \* @param nums 
143.      \* @param operators 
144.      \*/  
145.     private void compute(Vector<Double> nums, Vector<Operator> operators) \{  
146.         Double num2 = nums.remove(nums.size() - 1); // 第二个数字，当前队列的最后一个数字  
147.         Double num1 = nums.remove(nums.size() - 1); // 第一个数字，当前队列的最后一个数字  
148.         Double computeResult = operators.remove(operators.size() - 1).compute(  
149.                 num1, num2); // 取最后一个运算符进行计算  
150.         nums.add(computeResult); // 把计算结果重新放到队列的末端  
151.     \}  
152.       
153.     /\*\* 
154.      \* 取numStack的最顶上两个数字，operStack的最顶上一个运算符进行运算，然后把运算结果再放到numStack的最顶端 
155.      \* @param numStack  数字栈 
156.      \* @param operStack 操作栈 
157.      \*/  
158.     private void compute(Stack<Double> numStack, Stack<Operator> operStack) \{  
159.         Double num2 = numStack.pop(); // 弹出数字栈最顶上的数字作为运算的第二个数字  
160.         Double num1 = numStack.pop(); // 弹出数字栈最顶上的数字作为运算的第一个数字  
161.         Double computeResult = operStack.pop().compute(  
162.                 num1, num2); // 弹出操作栈最顶上的运算符进行计算  
163.         numStack.push(computeResult); // 把计算结果重新放到队列的末端  
164.     \}  
165.       
166.     /\*\* 
167.      \* 运算符 
168.      \*/  
169.     private enum Operator \{  
170.         /\*\* 
171.          \* 加 
172.          \*/  
173.         PLUS \{  
174.             @Override  
175.             public int priority() \{  
176.                 return 1;   
177.             \}  
178.   
179.             @Override  
180.             public double compute(double num1, double num2) \{  
181.                 return num1 + num2;   
182.             \}  
183.         \},  
184.         /\*\* 
185.          \* 减 
186.          \*/  
187.         MINUS \{  
188.             @Override  
189.             public int priority() \{  
190.                 return 1;   
191.             \}  
192.   
193.             @Override  
194.             public double compute(double num1, double num2) \{  
195.                 return num1 - num2;   
196.             \}  
197.         \},  
198.         /\*\* 
199.          \* 乘 
200.          \*/  
201.         MULTIPLY \{  
202.             @Override  
203.             public int priority() \{  
204.                 return 2;   
205.             \}  
206.   
207.             @Override  
208.             public double compute(double num1, double num2) \{  
209.                 return num1 \* num2;   
210.             \}  
211.         \},  
212.         /\*\* 
213.          \* 除 
214.          \*/  
215.         DIVIDE \{  
216.             @Override  
217.             public int priority() \{  
218.                 return 2;   
219.             \}  
220.   
221.             @Override  
222.             public double compute(double num1, double num2) \{  
223.                 return num1 / num2;   
224.             \}  
225.         \},  
226.         /\*\* 
227.          \* 括号 
228.          \*/  
229.         BRACKETS \{  
230.             @Override  
231.             public int priority() \{  
232.                 return 0;   
233.             \}  
234.   
235.             @Override  
236.             public double compute(double num1, double num2) \{  
237.                 return 0;   
238.             \}  
239.         \};  
240.         /\*\* 
241.          \* 对应的优先级 
242.          \* @return 
243.          \*/  
244.         public abstract int priority();  
245.   
246.         /\*\* 
247.          \* 计算两个数对应的运算结果 
248.          \* @param num1  第一个运算数 
249.          \* @param num2  第二个运算数 
250.          \* @return 
251.          \*/  
252.         public abstract double compute(double num1, double num2);  
253.     \}  
254. \}

[icon_star.png]: /images/20220613/cc91fc671bf44c97b1cf1b26fff722f8.png