【数据结构】三种方法计算中缀表达式

中缀表达式转后缀表达式并计算中缀表达式后缀表达式

镰刀韭菜

5774人浏览 · 2020-04-16 10:03:19

镰刀韭菜 · 2020-04-16 10:03:19 发布

中缀表达式转后缀表达式并计算

中缀表达式就是我们正常工作中写的表达式，如 a+(b-c)d ，编译系统将中缀表达式改写 abc-d+ ，这种运算符在操作数后面称为后缀表达式（也称逆波兰表达式）。

题目：输入一个中缀表达式，计算其结果。
输入的前提假设：
（1）只考虑+、-、*、/这四种运算符，中缀表达式中只有一种括号：（）；
（2）输入的中缀表达式中只有整数，没有小数；
（3）假定输入是合法的。

案例：1+ (2-3) * 4 + 6/3
提示：利用栈的“记忆”，符号都推入栈即可！
注意：计算一个中缀表达式需要知道运算符的优先级和结合性。乘除是高优先级，加减是低优先级，优先级相同时他们都是左结合的，也就是从左计算到右。有括号就要计算括号内的表达式。

中缀表达式转换为后缀表达式

利用栈来实现转换

转换过程需要用到栈，这里使用两个栈：stack 栈用来存放运算符，post 栈用来存放最后的后缀表达式。具体规则如下：
从左到右扫描中缀表达式：
若是操作数，直接存入 post 栈；
若是运算符：
（1）该运算符是左括号 ( , 则直接存入 stack 栈。
（2）该运算符是右括号 )，则将 stack 栈中 ( 前的所有运算符出栈，存入 post 栈。
（3）若该运算符为非括号，则将该运算符和 stack 栈顶运算符作比较：若高于栈顶运算符，则直接存入 stack 栈，否则将栈顶运算符出栈（从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止），存入 post 栈。
（4）当扫描完后，stack 栈中还有运算符时，则将所有运算符出栈，存入 post 栈。
例子：中缀表达式 a + b * c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。
具体过程如下：

扫描	stack栈	post栈
a	空	a
a+	+	a
a+b	+	ab
a+b*	+*	ab
a+b*c	+*	abc
a+b*c+	+	abc*+
a+b*c+(	+(	abc*+
a+b*c+(d	+(	abc*+d
a+bc+(d	+(*	abc*+d
a+bc+(de	+(*	abc*+de
a+bc+(de+	+(+	abc+de
a+bc+(de+f	+(+	abc+def
a+bc+(de+f)	+	abc+def+
a+bc+(de+f)*	+*	abc+def+
a+bc+(de+f)*g	+*	abc+def+g
a+bc+(de+f)*g#	空	abc*+def+g+

注意：表格中第6步，读到+,因为栈顶元素的优先级高，所以出栈，栈中下一个元素+优先级与读到的操作符+一样，所以也要弹出。然后再将读到的+压入栈中。第13步，读到)，则直接将栈中元素弹出直到遇到(为止。这里左括号前只有一个操作符+被弹出。

因此，对于案例中的表达式，将其转换为后缀表达式后的结果为123-4*+63/+。

另外，还有其他方法可以实现中缀表达式转后缀表达式

利用语法树

先将中缀表达式用二叉树表示出来，再后序遍历该二叉树，就得到其相应的后缀表达式。

加括号法

加括号法先将中缀表达式每步要计算的表达式加上括号，然后将每个运算符移到其所在括号的外面，最后，从左到右去掉括号后就是后缀表达式。
*示例： a+(b-c)d
加括号后： (a+((b-c)d))
移运算符： (a((bc)-d)*)+
去括号 abc-d+

计算后缀表达式

后缀表达式的计算就相当简单了。准备一个数字栈。从左到右扫描后缀表达式，如果是数字，放入数字栈。如果是符号，从数字栈中弹出两个数字，第一个取出的数字为右运算数，第二个为左运算数，进行运算。然后将结果放进数字栈中。如此反复，直到读完整个表达式后，留在数字栈中的那个数字就是最终结果。
例如：假定待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，则其求值过程如下：

遍历表达式，遇到数字首先放入栈，此时栈如下 6 5 2 3
接着读到+，则弹出3和2，执行2+3，将结果5压栈 6 5 5
读到8，压栈 6 5 5 8
读到 , 弹出8和5，执行58，将结果40压栈 6 5 40
读到 +,弹出40和5，执行5+40，将结果45压栈 6 45
读到 3,压栈 6 45 3
读到 +,弹出3和45，执行45+3，将结果48压栈 6 48
读到 ,弹出48和6，执行648，将结果288压栈 288

最后结果288
代码如下：

package DataStructure;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * 中缀表达式转后缀表达式并计算
 */
public class NifixExpression {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String exp = sc.nextLine();
            // 将中缀表达式转为List形式
            List<String> nifixExpression = nifix2List(exp);
            System.out.println("NifixExpression = " + nifixExpression);
            List<String> postfixExpression = nifix2postfix(nifixExpression);
            System.out.println("postfixExpression = " + postfixExpression);
            // 计算后缀表达式的值
            int reslut = calculate(postfixExpression);
            System.out.println(exp + " = " + reslut);
        }
    }

    /**
     * 根据后缀表达式计算结果
     *
     * @param postfixExpression
     * @return
     */
    private static int calculate(List<String> postfixExpression) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < postfixExpression.size(); i++) {
            String item = postfixExpression.get(i);
            if (isNumber(item)) {
                //是数字
                stack.push(Integer.parseInt(item));
            } else {
                //是操作符，取出栈顶两个元素
                int num2 = stack.pop();
                int num1 = stack.pop();
                int res = 0;
                switch (item) {
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                    default:
                        throw new RuntimeException("运算符错误！");
                }
                stack.push(res);
            }
        }
        return stack.pop();
    }

    /**
     * 将表达式转为List格式
     *
     * @param exp
     * @return
     */
    private static List<String> nifix2List(String exp) {
        int index = 0;
        List<String> list = new ArrayList<>();
        do {
            char chr = exp.charAt(index);
            // 从48到57对应ASCII的0到9数字
            if (chr <= 47 || chr >= 58) { //是操作符， 直接加入到list中
                index++;
                list.add(chr + "");
            } else if (chr > 47 && chr < 58) { //是数字，需要判断是否是多位
                String str = "";
                while (index < exp.length() && exp.charAt(index) > 47 && exp.charAt(index) < 58) {
                    str += exp.charAt(index);
                    index++;
                }
                list.add(str);
            }
        } while (index < exp.length());
        return list;
    }

    private static List<String> nifix2postfix(List<String> exp) {
        // 创建一个栈用来保存操作符
        Stack<String> operatorStack = new Stack<>();
        // 创建一个List用来保存后缀表达式
        List<String> sufffixList = new ArrayList<>();
        for (String item : exp) {
            //得到数或操作符
            if (isOperator(item)) {
                //是操作符，判断操作符栈是否为空
                if (operatorStack.isEmpty() || "(".equals(operatorStack.peek()) || priority(item) > priority(operatorStack.peek())) {
                    //为空或者栈顶元素为左括号或者当前操作符大于栈顶操作符的优先级则直接压栈
                    operatorStack.push(item);
                } else {
                    //否则将栈中元素出栈入队，直到遇到大于当前操作符的优先级或者遇到左括号
                    while (!operatorStack.isEmpty() && !"(".equals(operatorStack.peek())) {
                        if (priority(item) <= priority(operatorStack.peek())) {
                            sufffixList.add(operatorStack.pop());
                        }
                    }
                    // 当前操作符压栈
                    operatorStack.push(item);
                }
            } else if ((isNumber(item))) {
                //是数字则直接入队
                sufffixList.add(item);
            } else if ("(".equals(item)) {
                //是左括号，直接压栈
                operatorStack.push(item);
            } else if (")".equals(item)) {
                //是右括号，则将栈中元素弹出，直到遇到左括号，左括号出栈，但不入队
                while (!operatorStack.isEmpty()) {
                    if ("(".equals(operatorStack.peek())) {
                        operatorStack.pop();
                        break;
                    } else {
                        sufffixList.add(operatorStack.pop());
                    }
                }
            } else {
                throw new RuntimeException("有非法字符！");
            }
        }
        //循环完毕，如果操作符栈中元素不为空，将栈中元素出栈入队
        while (!operatorStack.isEmpty()) {
            sufffixList.add(operatorStack.pop());
        }
        return sufffixList;
    }

    /**
     * 判断是否为数字
     *
     * @param item
     * @return
     */
    private static boolean isNumber(String item) {
        return item.matches("\\d+");
    }

    /**
     * 获取操作符的运算优先级
     *
     * @param item
     * @return
     */
    private static int priority(String item) {
        if (item.equals("*") || item.equals("/")) {
            return 1;
        } else if (item.equals("+") || item.equals("-")) {
            return 0;
        }
        return -1;
    }

    /**
     * 判断是否为操作符
     *
     * @param item
     * @return
     */
    private static boolean isOperator(String item) {
        return item.equals("+") || item.equals("-") || item.equals("*") || item.equals("/");
    }
}