数据结构与算法之前缀-中缀-后缀表达式

清疚 2021-12-08 22:02 263阅读 0赞

### 前言 ###

在上篇文章我们介绍了栈的基本概念，演示了如何来实现了一个简单的栈。并基于栈实现了一个综合计算器，这个计算器只支持简单的`+、-、*、/`，无法支持加小括号来控制运算的优先级，要控制运算优先级，首先要了解本文标题所说的几个表达式，下面我将一一介绍。

## 前缀表达式(波兰表达式) ##

> **前缀表达式**是**一种没有括号的算术表达式**，**前缀表达式也称波兰表达式**，前缀表达式的运算符位于操作数之前。例如：`(3+4)×5-6` 对应的前缀表达式是：`- × + 3 4 5 6`

前缀表达式求值方式：  
对前缀表达式求值，要**从右至左扫描表达式**，若当前字符是数字则将数字压入栈中，若为运算符，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和次顶元素，并将结果入栈；重复上述过程直到扫描到表达式最左端时扫描结束，最后运算得出的值即为表达式的结果。

举例：`(3+4)×5-6` 对应的前缀表达式是：`- × + 3 4 5 6` ,针对前缀表达式求值步骤如下：

1.  从右至左扫描表达式，将`6、5、4、3`压入栈中；
2.  遇到`+`运算符，因此弹出`3`和`4`（`3`为栈顶元素，`4`为次顶元素），计算出`3+4`的值，等于7，再将`7`入栈；
3.  接下来是`×`运算符，因此弹出`7`和`5`，计算出`7×5=35`，将`35`入栈；
4.  最后是`-`运算符，计算出`35-6`的值，即`29`，由此得出最终结果；

代码示例：

public class PrefixExpressionCal {
    
        public static void main(String[] args) {
            ArrayStack numberStack = new ArrayStack(10); // 数据栈
            ArrayStack operatorStack = new ArrayStack(10); // 运算符栈
            String expression = "6*3*9-8+5-7"; // 运算表达式
            // 定义相关临时辅助变量
            int index = 0;
            int num1 = 0;
            int num2 = 0;
            int oper = 0;
            int res = 0;
            char ch = ' ';
            String keepNum = "";
            while (true) {
                // 遍历依次得到表达式中的每一个字符
                ch = expression.substring(index, index + 1).charAt(0);
                // 判断ch是什么
                if (PrefixExpressionCal.isOperator(ch)) {// 如果是运算符
                    // 判断当前运算符栈是否为空
                    if (!operatorStack.isEmpty()) {
                        // 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中取出两个数,再从符号栈中取出一个符号，进行运算，
                        // 将得到的结果，入数据栈，然后将当前的操作符入符号栈
                        if (PrefixExpressionCal.getPriority(ch) <= PrefixExpressionCal.getPriority(operatorStack.peek())) {
                            num1 = numberStack.pop();
                            num2 = numberStack.pop();
                            oper = operatorStack.pop();
                            // 进行计算
                            res = PrefixExpressionCal.cal(num1, num2, oper);
                            // 将计算得到的结果放入数据栈
                            numberStack.push(res);
                            // 将当前的运算符放入运算符栈
                            operatorStack.push(ch);
                        } else {
                            // 如果当前的运算符的优先级大于栈中的运算符，就直接放入运算符栈
                            operatorStack.push(ch);
                        }
                    } else {
                        // 直接入运算符栈
                        operatorStack.push(ch); // 1 + 3
                    }
                } else { // 如果是数字直接入数据栈
                    // 处理多位数
                    keepNum += ch;
    
                    // 判断是否是表达式最后一个字符，如果是，直接入栈
                    if (index == expression.length() - 1) {
                        numberStack.push(Integer.parseInt(keepNum));
                    } else {
                        // 判断下一个字符是不是数字，如果是数字，就继续遍历，如果是运算符，就直接入栈
                        if (PrefixExpressionCal.isOperator(expression.substring(index + 1, index + 2).charAt(0))) {
                            numberStack.push(Integer.parseInt(keepNum));
                            // 清空
                            keepNum = "";
                        }
                    }
                }
                // 让index+1，判断表达式是否遍历完了
                index++;
                if (index >= expression.length()) {
                    break;
                }
            }
    
            // 当表达式遍历完了之后，就顺序从数据栈和运算符栈中取出相应的数字和运算符进行计算
            while (true) {
                // 如果运算符栈为空，则代表计算到了最后的结果，数据栈中就只有一个结果数据了
                if (operatorStack.isEmpty()) {
                    break;
                }
                num1 = numberStack.pop();
                num2 = numberStack.pop();
                oper = operatorStack.pop();
                // 计算结果
                res = PrefixExpressionCal.cal(num1, num2, oper);
                numberStack.push(res);// 最终的结果
            }
            System.out.printf("运算表达式 %s = %d", expression, numberStack.pop());
        }
    
        /**
         * 返回运算符的优先级
         *
         * @param operator 运算符
         * @return
         */
        public static int getPriority(int operator) {
            if (operator == '*' || operator == '/') {
                return 1;
            } else if (operator == '+' || operator == '-') {
                return 0;
            } else {
                return -1; // 目前只支持 +, - , * , /
            }
        }
    
        /**
         * 是否是运算符判断
         *
         * @param val
         * @return
         */
        public static boolean isOperator(char val) {
            return val == '+' || val == '-' || val == '*' || val == '/';
        }
    
        /**
         * 计算
         *
         * @param num1 数据一
         * @param num2 数据二
         * @param oper 运算符
         * @return
         */
        public static int cal(int num1, int num2, int oper) {
            int result = 0;
            switch (oper) {
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num2 - num1;
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                case '/':
                    result = num2 / num1;
                    break;
                default:
                    break;
            }
            return result;
        }
    }

## 中缀表达式 ##

> **中缀表达式**是**一个通用的算术或逻辑公式表示方法**， 操作符是以中缀形式处于操作数的中间（例：`3 + 4`），中缀表达式是人们常用的算术表示方法。但是中缀表达式不容易被计算机解析(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)。

中缀表达式转后缀表达式  
实现方式有多种，可自由发挥  
转换步骤：

1.  初始化一个栈和一个list；
2.  从左至右扫描中缀表达式；
3.  遇到操作数时，将其添加到list中；
4.  如果当前字符是左括号`'('`时，直接入栈；
5.  遇到运算符时，比较其与栈顶运算符的优先级：  
    4.1. 如果此时栈为空，则直接将此运算符入栈；  
    4.2. 如果栈不为空，并且运算符的优先级比栈顶运算符的优先级高，也将运算符入栈。否则，将栈顶的运算符弹出并加入到list中，并重复此步骤，直到条件不满足时结束；
6.  遇到右括号`‘)’`时，依次弹出栈顶的运算符，加入到list中，直到遇到左括号为止，并消除左括号；
7.  重复2～6步骤，直到扫描完整个表达式；
8.  将栈中剩余的运算符弹出加入到list中；
9.  此时list中数据则是中缀表达式对应的后缀表达式；

代码示例：

public class PolandNotaion {
    
        public static void main(String[] args) {
            // 定义一个中缀表达式
            String suffixExpression = "1+((2+3)*4)-5";
            List<String> dataList = parseSuffixExpression(suffixExpression);
            
            System.out.println("dataList：" + dataList);
        }
    	
        /**
         * 中缀表达式转list
         *
         * @param expression 中缀表达式
         * @return
         */
        public static List<String> toExpressionList(String expression) {
            List<String> result = new ArrayList<>();
            String temp = "";
            for (int i = 0; i < expression.length(); i++) {
                String str = expression.substring(i, i + 1);
                // 使用正则表达示判断是否是数字
                if (!str.matches("\\d+")) {
                    result.add(str);
                } else {
                    // 判断是否是表达式最后一个字符，如果是，直接放入list
                    if (i == expression.length() - 1) {
                        result.add(str);
                        continue;
                    }
    
                    temp += str;
                    // 处理多位数
                    String nextStr = expression.substring(i + 1, i + 2);
                    if (!nextStr.matches("\\d+")) {
                        result.add(temp);
                        temp = "";
                    }
                }
            }
            return result;
        }
    
    
        /**
         * 中缀表达式转后缀表达式
         *
         * @param expression 中缀表达式
         * @return
         */
        public static List<String> parseSuffixExpression(String expression){
            List<String> result = new ArrayList<>();
            // 中缀表达式转list
            List<String> toInfixExpressionList = toExpressionList(expression);
    
            Stack<String> stack = new Stack<>();
    
            for (String item : toInfixExpressionList) {
                if (item.matches("\\d+")) {
                    result.add(item);
                } else if ("(".equals(item)) {
                    stack.push(item);
                } else if (")".equals(item)) {
                    // 如果是右括号，则依次弹出栈顶的运算符，并放入result list中，直到遇到左括号为止，此时将这一对括号丢弃
                    while (!"(".equals(stack.peek())) {
                        result.add(stack.pop());
                    }
                    stack.pop(); // 消除左括号
                } else {
                    // 当item的优先级小于等于栈顶的运算符，将栈顶的运算符弹出并加入到result中，并重复此步骤，直到条件不满足时结束
                    while (stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(item)) {
                        result.add(stack.pop());
                    }
    
                    // 还需要将item入栈
                    stack.push(item);
                }
            }
    
            // 将栈中剩余的运算符弹出放入result中
            while (stack.size() != 0){
                result.add(stack.pop());
            }
            return result;
        }
    
        /**
         * 返回运算符的优先级
         *
         * @param operator 运算符
         * @return
         */
        public static int getPriority(int operator) {
            if (operator == '*' || operator == '/') {
                return 1;
            } else if (operator == '+' || operator == '-') {
                return 0;
            } else {
                return -1; // 目前只支持 +, - , * , /
            }
        }
    }

## 后缀表达式(逆波兰表达式) ##

> **后缀表达式**，又称**逆波兰表达式**，与前缀表达式相似，只是运算符位于操作数后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。例如：`(3+4)×5-6`对应的后缀表达式就是: `3 4 + 5 × 6 –`

中缀转后缀示例：

<table> 
 <thead> 
  <tr> 
   <th align="left">中缀表达式</th> 
   <th align="left">后缀表达式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">a+b</td> 
   <td align="left">a b +</td> 
  </tr> 
  <tr> 
   <td align="left">a+(b-c)</td> 
   <td align="left">a b c - +</td> 
  </tr> 
  <tr> 
   <td align="left">aa+(b-c)*d</td> 
   <td align="left">a b c – d * +</td> 
  </tr> 
  <tr> 
   <td align="left">a+d*(b-c)</td> 
   <td align="left">a d b c - * +</td> 
  </tr> 
  <tr> 
   <td align="left">a=1+3</td> 
   <td align="left">a 1 3 + =</td> 
  </tr> 
 </tbody> 
</table>

后缀表达式求值方式：**从左至右扫描表达式**，遇到数字时，将数字压入栈中，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到扫描到表达式最左端时扫描结束，最后运算得出的值即为表达式的结果

举例： `(3+4)×5-6` 对应的后缀表达式就是`3 4 + 5 × 6 -`, 针对后缀表达式求值步骤如下：

1.  从左至右扫描，将`3`和`4`压入栈中；
2.  遇到`+`运算符，因此弹出`4`和`3`（`4`为栈顶元素，`3`为次顶元素），计算出`3+4`的值，等于`7`，再将`7`入栈；
3.  将5入栈；
4.  接下来是`×`运算符，因此弹出`5`和`7`，计算出`7×5=35`，将`35`入栈；
5.  将`6`入栈；
6.  最后是`-`运算符，计算出`35-6`的值，即`29`，由此得出最终结果

此处注意：后缀表达式是将后弹出的数在前与先弹出的数进行运算；中缀表达式将先弹出来的数在前与后弹出的数进行运算

代码示例：

public class PolandNotaion {
    
        public static void main(String[] args) {
            // 定义一个中缀表达式
            String suffixExpression = "1+((2+3)*4)-5";
            List<String> dataList = parseSuffixExpression(suffixExpression);
    
            System.out.println("dataList：" + dataList);
            System.out.println("运算结果：" + calculator(dataList));
        }
        
        /**
         * 中缀表达式转list
         *
         * @param expression 中缀表达式
         * @return
         */
        public static List<String> toExpressionList(String expression) {
            List<String> result = new ArrayList<>();
            String temp = "";
            for (int i = 0; i < expression.length(); i++) {
                String str = expression.substring(i, i + 1);
                // 使用正则表达示判断是否是数字
                if (!str.matches("\\d+")) {
                    result.add(str);
                } else {
                    // 判断是否是表达式最后一个字符，如果是，直接放入list
                    if (i == expression.length() - 1) {
                        result.add(str);
                        continue;
                    }
    
                    temp += str;
                    // 处理多位数
                    String nextStr = expression.substring(i + 1, i + 2);
                    if (!nextStr.matches("\\d+")) {
                        result.add(temp);
                        temp = "";
                    }
                }
            }
            return result;
        }
    
    
        /**
         * 中缀表达式转后缀表达式
         *
         * @param expression 中缀表达式
         * @return
         */
        public static List<String> parseSuffixExpression(String expression){
            List<String> result = new ArrayList<>();
            // 中缀表达式转list
            List<String> toInfixExpressionList = toExpressionList(expression);
    
            Stack<String> stack = new Stack<>();
    
            for (String item : toInfixExpressionList) {
                if (item.matches("\\d+")) {
                    result.add(item);
                } else if ("(".equals(item)) {
                    stack.push(item);
                } else if (")".equals(item)) {
                    // 如果是右括号，则依次弹出栈顶的运算符，并放入result list中，直到遇到左括号为止，此时将这一对括号丢弃
                    while (!"(".equals(stack.peek())) {
                        result.add(stack.pop());
                    }
                    stack.pop(); // 消除左括号
                } else {
                    // 当item的优先级小于等于栈顶的运算符，将栈顶的运算符弹出并加入到result中，并重复此步骤，直到条件不满足时结束
                    while (stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(item)) {
                        result.add(stack.pop());
                    }
    
                    // 还需要将item入栈
                    stack.push(item);
                }
            }
    
            // 将栈中剩余的运算符弹出放入result中
            while (stack.size() != 0){
                result.add(stack.pop());
            }
            return result;
        }
    
        /**
         * 返回运算符的优先级
         *
         * @param operator 运算符
         * @return
         */
        public static int getPriority(int operator) {
            if (operator == '*' || operator == '/') {
                return 1;
            } else if (operator == '+' || operator == '-') {
                return 0;
            } else {
                return -1; // 目前只支持 +, - , * , /
            }
        }
    
        /**
         * 根据后缀表达式计算结果
         *
         * 从左至右扫描，如果是数字则压入栈中，如果是运算符则取出栈顶元素和次栈顶元素进行运算，并将运算结果入栈
         * 重复上述过程，直到循环结束，最终留到栈中的就是运算结果
         *
         * @param dataList
         * @return
         */
        public static int calculator(List<String> dataList) {
            Stack<String> stack = new Stack<>();
            for (String item : dataList) {
                // 使用正则表达示判断是否是数字
                if (item.matches("\\d+")) {
                    // 入栈
                    stack.push(item);
                } else {
                    int num1 = Integer.parseInt(stack.pop());
                    int num2 = Integer.parseInt(stack.pop());
    
                    int calRsult = cal(num2, num1, item.charAt(0));
                    // 将计算结果入栈
                    stack.push(String.valueOf(calRsult));
                }
            }
            return Integer.parseInt(stack.pop());
        }
    
        /**
         * 计算
         *
         * @param num1 数据一
         * @param num2 数据二
         * @param oper 运算符
         * @return
         */
        public static int cal(int num1, int num2, int oper) {
            int result = 0;
            switch (oper) {
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num1 - num2;
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                case '/':
                    result = num1 / num2;
                    break;
                default:
                    break;
            }
            return result;
        }
    }