java数据结构与算法总结(四)--Java实现表达式计算（中缀表达式转化为后缀表达式/逆波兰式）

朴灿烈づ我的快乐病毒、 2023-02-14 13:07 107阅读 0赞

在做一道算法题时遇到该问题，写一个计算器其中有加减乘除和括号，用最快的算法算出来。后来根据答案想了下用下面的算法是复合答案的意思。

**定义：**

*  **中缀表达式：**

我们平时写的数学表达式一般为中缀表达式，如“5+2\*(3\*(3-1\*2+1))”，直接拿中缀表达式直接让计算机计算表达式的结果并不能做到。

*  **后缀表达式：**

把中缀表达表达式“5+2\*(3\*(3-1\*2+1))”转化“523312\*-1+\*\*+”这样的形式，就是后缀表达式。这种记法叫做后缀（postfix）或逆波兰（reverse Polish）记法。计算这个问题最容易的方法就是使用一个栈。  
**转换方法：**

1.  按次序读取中缀表达式的字符。
2.  读到一个操作数的时候，立即放入到输出中。
3.  读到操作符“+”，“-”，“\*”，“/”，则从栈中弹出栈元素并输出，直到遇到优先级更低或者“(”的为止操作符为止（该元素不出栈）。
4.  读到操作符“(”，则直接把“(”压入栈中。
5.  读到操作符“)”，则从栈中弹出栈元素并输出，直到遇到第一个“(”为止。其中“(”不再添加到输出中，而是直接舍弃。
6.  当输入为空时，把栈里的操作符全部依次弹出并输出。

**举例：**

![20200602222255661.png][]

<table> 
 <tbody> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;width:54pt;">操作</td> 
 <td style="text-align:left;vertical-align:middle;width:460.2pt;">说明</td> 
 <td style="text-align:left;vertical-align:middle;width:117pt;">栈</td> 
 <td style="text-align:left;vertical-align:middle;width:157.8pt;">输出</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取5</td> 
 <td style="text-align:left;vertical-align:middle;">把操作数直接输出</td> 
 <td style="text-align:left;vertical-align:middle;">&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;">5</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取+</td> 
 <td style="text-align:left;vertical-align:middle;">栈为空，把操作符压入栈</td> 
 <td style="text-align:left;vertical-align:middle;">+</td> 
 <td style="text-align:left;vertical-align:middle;">5</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取2</td> 
 <td style="text-align:left;vertical-align:middle;">把操作数直接输出</td> 
 <td style="text-align:left;vertical-align:middle;">+</td> 
 <td style="text-align:left;vertical-align:middle;">52</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取*</td> 
 <td style="text-align:left;vertical-align:middle;">栈顶元素为+，优先级低于*，把操作符压入栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*</td> 
 <td style="text-align:left;vertical-align:middle;">52</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取(</td> 
 <td style="text-align:left;vertical-align:middle;">把 ( 直接压入栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*(</td> 
 <td style="text-align:left;vertical-align:middle;">52</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取3</td> 
 <td style="text-align:left;vertical-align:middle;">把操作数直接输出</td> 
 <td style="text-align:left;vertical-align:middle;">+*(</td> 
 <td style="text-align:left;vertical-align:middle;">523</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取*</td> 
 <td style="text-align:left;vertical-align:middle;">栈顶元素为(，把操作符压入栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*</td> 
 <td style="text-align:left;vertical-align:middle;">523</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取(</td> 
 <td style="text-align:left;vertical-align:middle;">把 ( 直接压入栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(</td> 
 <td style="text-align:left;vertical-align:middle;">523</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取3</td> 
 <td style="text-align:left;vertical-align:middle;">把操作数直接输出</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(</td> 
 <td style="text-align:left;vertical-align:middle;">5233</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取-</td> 
 <td style="text-align:left;vertical-align:middle;">栈顶元素为(，把操作符压入栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(-</td> 
 <td style="text-align:left;vertical-align:middle;">5233</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取1</td> 
 <td style="text-align:left;vertical-align:middle;">把操作数直接输出</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(-</td> 
 <td style="text-align:left;vertical-align:middle;">52331</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取*</td> 
 <td style="text-align:left;vertical-align:middle;">栈顶元素为-，优先级低于*，把操作符压入栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(-*</td> 
 <td style="text-align:left;vertical-align:middle;">52331</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取2</td> 
 <td style="text-align:left;vertical-align:middle;">把操作数直接输出</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(-*</td> 
 <td style="text-align:left;vertical-align:middle;">523312</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取+</td> 
 <td style="text-align:left;vertical-align:middle;">栈顶元素为*，优先级高于+，以此弹出*,-到输出，到 ( 停止，把操作符压入栈中</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(+</td> 
 <td style="text-align:left;vertical-align:middle;">523312*-</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取1</td> 
 <td style="text-align:left;vertical-align:middle;">把操作数直接输出</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*(+</td> 
 <td style="text-align:left;vertical-align:middle;">523312*-1</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取)</td> 
 <td style="text-align:left;vertical-align:middle;">从栈中弹出+到输出，遇到第一个 ( 停止，把 ( 弹出栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*(*</td> 
 <td style="text-align:left;vertical-align:middle;">523312*-1+</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">读取)</td> 
 <td style="text-align:left;vertical-align:middle;">从栈中弹出*到输出，遇到第一个 ( 停止，把 ( 弹出栈</td> 
 <td style="text-align:left;vertical-align:middle;">+*</td> 
 <td style="text-align:left;vertical-align:middle;">523312*-1+*</td> 
 </tr> 
 <tr> 
 <td style="text-align:left;vertical-align:middle;">结束读取</td> 
 <td style="text-align:left;vertical-align:middle;">把栈中的元素全部弹出到输出</td> 
 <td style="text-align:left;vertical-align:middle;">&nbsp;</td> 
 <td style="text-align:left;vertical-align:middle;">523312*-1+**+</td> 
 </tr> 
 </tbody> 
</table>

![20200602222732287.png][]

### 后缀表达式的计算： ###

1.  按次序读取后缀表达式的每一个字符。
2.  读取到操作数时，把操作数压入栈中。
3.  读取到操作符时，对栈顶的2个操作数做相应运算，要**注意操作数的前后顺序**。结果压入栈中。
4.  读取完所有的字符后，弹出栈。得到的值就是所求结果。

### 代码： ###

import java.util.Stack; 
 
 
 public class Main {
 
 static Stack<Character> op = new Stack<>();
 
 public static Float getv(char op, Float f1, Float f2){
 if(op == '+') return f2 + f1;
 else if(op == '-') return f2 - f1;
 else if(op == '*') return f2 * f1;
 else if(op == '/') return f2 / f1;
 else return Float.valueOf(-0);
 }
 
 /**
 * calculate the value of the reverse Polish expression
 * @param rp - reverse Polish expression
 * @return - result of the expression
 */
 public static float calrp(String rp){
 Stack<Float> v = new Stack<>();
 char[] arr = rp.toCharArray();
 int len = arr.length;
 for(int i = 0; i < len; i++){
 Character ch = arr[i];
 
 // if is operand, push to the stack
 if(ch >= '0' && ch <= '9') v.push(Float.valueOf(ch - '0'));
 
 // if is operator, calculate the result
 // with top 2 operands in the stack,
 // push the result into the stack
 else v.push(getv(ch, v.pop(), v.pop()));
 }
 return v.pop();
 }
 
 /**
 * from infix to postfix
 * @param s - String in the form of infix
 * @return String in the form of postfix
 */
 public static String getrp(String s){
 char[] arr = s.toCharArray();
 int len = arr.length;
 String out = "";
 
 for(int i = 0; i < len; i++){
 char ch = arr[i];
 if(ch == ' ') continue;
 
 // if is operand, add to 
 // the output stream directly
 if(ch >= '0' && ch <= '9') {
 out+=ch;
 continue;
 }
 
 //if is '(', push to the stack directly
 if(ch == '(') op.push(ch);
 
 //if is '+' or '-', pop the operator 
 // from the stack until '(' and add to 
 // the output stream
 //push the operator to the stack
 if(ch == '+' || ch == '-'){
 while(!op.empty() && (op.peek() != '(')) 
 out+=op.pop();
 op.push(ch);
 continue;
 }
 
 //if is '*' or '/', pop the operator stack and 
 // add to the output stream 
 // until lower priority or '('
 //push the operator to the stack
 if(ch == '*' || ch == '/'){
 while(!op.empty() && (op.peek() == '*' || op.peek() == '/')) 
 out+=op.pop();
 op.push(ch);
 continue;
 }
 
 //if is ')' pop the operator stack and 
 // add to the output stream until '(', 
 // pop '('
 if(ch == ')'){
 while(!op.empty() && op.peek() != '(') 
 out += op.pop();
 op.pop();
 continue;
 }
 }
 while(!op.empty()) out += op.pop();
 return out;
 }
 
 public static void main(String[] args){
 //constraint: the operand should be 
 // equal or greater than 0 
 // but equal or less than 9
 String exp = "5+2*(3*(2-1))";
 System.out.println(calrp(getrp(exp)));
 }
 
 }

### 输出： ###

11.0

————————————————  
版权声明：本文为CSDN博主「Ring\_k」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/ring\_k/article/details/79598961

[20200602222255661.png]: https://img-blog.csdnimg.cn/20200602222255661.png
[20200602222732287.png]: https://img-blog.csdnimg.cn/20200602222732287.png