逆波兰算法、中缀表达式转后缀表达式

一、前、中、后缀表达 前缀表达式(波兰表达式、Prefix expression)

又称为波兰表达式，前缀表达式的运算符位于操作数之前

例如：(3 + 4) * 5 - 6对应的前缀表达式：- * + 3 4 5 6

中缀表达式(Infix expression)

中缀表达式就是常见的运算表达式，中缀表达式的求值往往是人们所熟悉的，但是对计算机来说却不好操作，一般将中缀表达式转换成其他表达式(一般转换成后缀表达式)

例如：(3 + 4) * 5 - 6

后缀表达式(逆波兰表达式、Postfix expression)

又称逆波兰表达式，后缀表达式的运算符位于操作数之后

例如：(3 + 4) * 5 - 6对应的后缀表达式为：3 4 + 5 * 6 -

二、中缀表达式转前、后缀表达式(手算) 转换过程

中缀表达式为：a + b * c - ( d + e )

1. 使用按照运算符的优先级对所有的运算单位加括号
   操作完成后式子变成： ( ( a + ( b * c ) ) - ( d + e ) )
2. 中缀表达式转前缀表达式：
   1）将运算符移动到对应括号之前：- ( + ( a * ( b c ) ) + ( d e ) )
   2）去掉括号：- + a * b c + d e
   3）转换完成
3. 中缀表达式转后缀表达式：
   1）将运算符移动到对应括号之后：( ( a ( b c ) * ) + ( d e ) + ) -
   2）去掉括号：a b c * + d e + -
   3）转换完成

三、中缀表达式转后缀表达式(代码实现) 算法思路

1.初始化两个栈:运算符栈operStack和存储结果的栈resStack
2.从左至右扫描中缀表达式
3.遇到操作数时(数字),直接将其压入栈resStack
4.遇到运算符时(+、-、*、/),比较其与operStack栈顶运算符的优先级
	4.1 如果operStack为空,或operStack栈顶运算符为左括号"(",则直接将此运算符压入栈operStack;
	4.2 否则,若优先级比operStack栈顶运算符优先级高,则将此运算符压入栈operStack;
	4.3 否则,将operStack栈顶的运算符弹出并压入到栈resStack,再次转到4与operStack中新的栈顶运算符相比较
5.遇到括号时:
	5.1 如果是左括号("("),则直接压入栈resStack
	5.2 如果是左括号(")"),则依次弹出operStack栈顶的运算符,并压入resStack,直到遇到左括号为止,并且把左括号弹出栈operStack,此时这一对括号丢弃
6.重复步骤2到5,直到遍历完整个表达式
7.将operStack中剩余的运算符依次弹出并压入resStack
8.依次弹出resStack中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

代码实现

public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) {
    // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack
    Stack<String> operStack = new Stack<>();
    Stack<String> resStack = new Stack<>();

    // step2:从左至右扫描中缀表达式
    for (String item : tokens) {
        if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时
            if (operStack.isEmpty() || "(".equals(operStack.peek())) {
                operStack.push(item);
            } else if (priority(item) > priority(operStack.peek())) {
                operStack.push(item);
            } else { // 当前操作符比栈顶操作符 优先级小或者相等
                while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) {
                    resStack.push(operStack.pop());
                }
                // 还需将item压入operStack栈
                operStack.push(item);
            }
        } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时
            // 如果是左括号,则直接压入numStack
            if ("(".equals(item)) {
                operStack.push(item);
            }
            // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃
            if (")".equals(item)) {
                while (!"(".equals(operStack.peek())) {
                    resStack.push(operStack.pop());
                }
                // 此时operStack栈顶元素为(,将其弹出
                operStack.pop();
            }
        } else { // 数字的话,直接压入resStack
            resStack.push(item);
        }
    }
    // step3:将numStack中剩余的运算符依次弹出并压入resStack
    while (!operStack.isEmpty()) {
        resStack.push(operStack.pop());
    }

    // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式
    ArrayList<String> list = new ArrayList<>();
    while (!resStack.isEmpty()) {
        list.add(resStack.pop());
    }
    Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式

    return list;
}

public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) {
    // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack
    Stack<String> operStack = new Stack<>();
    Stack<String> resStack = new Stack<>();

    // step2:从左至右扫描中缀表达式
    for (String item : tokens) {
        if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时
            if (operStack.isEmpty() || "(".equals(operStack.peek())) {
                operStack.push(item);
            } else if (priority(item) > priority(operStack.peek())) {
                operStack.push(item);
            } else { // 当前操作符比栈顶操作符 优先级小或者相等
                while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) {
                    resStack.push(operStack.pop());
                }
                // 还需将item压入operStack栈
                operStack.push(item);
            }
        } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时
            // 如果是左括号,则直接压入numStack
            if ("(".equals(item)) {
                operStack.push(item);
            }
            // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃
            if (")".equals(item)) {
                while (!"(".equals(operStack.peek())) {
                    resStack.push(operStack.pop());
                }
                // 此时operStack栈顶元素为(,将其弹出
                operStack.pop();
            }
        } else { // 数字的话,直接压入resStack
            resStack.push(item);
        }
    }
    // step3:将numStack中剩余的运算符依次弹出并压入resStack
    while (!operStack.isEmpty()) {
        resStack.push(operStack.pop());
    }

    // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式
    ArrayList<String> list = new ArrayList<>();
    while (!resStack.isEmpty()) {
        list.add(resStack.pop());
    }
    Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式

    return list;
}

public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) {
    // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack
    Stack<String> operStack = new Stack<>();
    Stack<String> resStack = new Stack<>();

    // step2:从左至右扫描中缀表达式
    for (String item : tokens) {
        if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时
            if (operStack.isEmpty() || "(".equals(operStack.peek())) {
                operStack.push(item);
            } else if (priority(item) > priority(operStack.peek())) {
                operStack.push(item);
            } else { // 当前操作符比栈顶操作符 优先级小或者相等
                while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) {
                    resStack.push(operStack.pop());
                }
                // 还需将item压入operStack栈
                operStack.push(item);
            }
        } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时
            // 如果是左括号,则直接压入numStack
            if ("(".equals(item)) {
                operStack.push(item);
            }
            // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃
            if (")".equals(item)) {
                while (!"(".equals(operStack.peek())) {
                    resStack.push(operStack.pop());
                }
                // 此时operStack栈顶元素为(,将其弹出
                operStack.pop();
            }
        } else { // 数字的话,直接压入resStack
            resStack.push(item);
        }
    }
    // step3:将numStack中剩余的运算符依次弹出并压入resStack
    while (!operStack.isEmpty()) {
        resStack.push(operStack.pop());
    }

    // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式
    ArrayList<String> list = new ArrayList<>();
    while (!resStack.isEmpty()) {
        list.add(resStack.pop());
    }
    Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式

    return list;
}

测试

public static void main(String[] args) {
    ArrayList<String> infixList = new ArrayList<>(); // 中缀表达式
    String infixExpression = "1+((2+3)*4)-5";

    char[] chs = infixExpression.toCharArray();
    for (char ch : chs) {
        infixList.add(ch + ""); // char转String的小技巧
    }
    System.out.println("中缀表达式:" + infixList);

    ArrayList<String> postfixList = InfixChangeToPostfix(infixList);
    System.out.println("后缀表达式:" + postfixList);
}

运行结果

中缀表达式:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
后缀表达式:[1, 2, 3, +, 4, *, +, 5, -]

四、后缀表达式求值(逆波兰表达式求值)

即根据逆波兰表示法(后缀表达式)，求表达式的值。

算法思路

从左至右扫描表达式
若遇到数字,则将数字压入堆栈
遇到运算符时,弹出栈顶的两个数(分别为栈顶元素和次顶元素),用元素对它们做相应的计算,并将结果入栈
重复上述过程直到表达式最右端
最后栈的最后一个元素即为表达式的结果

样例

代码实现

// 后缀表达式求值(逆波兰表达式求值)
public static int evalRPN(ArrayList<String> list) {
    Stack<Integer> stack = new Stack<>();
    for (String item : list) {
        if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) {
            int num1 = stack.pop(); // 栈顶元素
            int num2 = stack.pop(); // 次顶元素
            switch (item) {
                case "+" : stack.push(num1 + num2);break;
                case "-" : stack.push(num2 - num1);break;
                case "*" : stack.push(num1 * num2);break;
                case "/" : stack.push(num2 / num1);break;
            }
        } else {
            stack.push(Integer.parseInt(item));
        }
    }
    return stack.pop();
}

对应LeetCode一题：LeetCode150. 逆波兰表达式求值

五、中缀表达式转后缀表达式并计算结果(代码实现)

前提：操作数为整数并且运算符为+ 、 - 、 * 、 /

代码实现

package 栈;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class 中缀表达式转后缀表达式 {
    public static void main(String[] args) {
        ArrayList<String> infixList = new ArrayList<>(); // 中缀表达式
        String infixExpression = "1+((2+3)*4)-5";

        char[] chs = infixExpression.toCharArray();
        for (char ch : chs) {
            infixList.add(ch + ""); // char转String的小技巧
        }
        System.out.println("中缀表达式:" + infixList);

        ArrayList<String> postfixList = InfixChangeToPostfix(infixList);
        System.out.println("后缀表达式:" + postfixList);

        int res = evalRPN(postfixList);
        System.out.println("后缀表达式的值为:" + res);
    }

    public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) {
        // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack
        Stack<String> operStack = new Stack<>();
        Stack<String> resStack = new Stack<>();

        // step2:从左至右扫描中缀表达式
        for (String item : tokens) {
            if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时
                if (operStack.isEmpty() || "(".equals(operStack.peek())) {
                    operStack.push(item);
                } else if (priority(item) > priority(operStack.peek())) {
                    operStack.push(item);
                } else { // 当前操作符比栈顶操作符 优先级小或者相等
                    while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) {
                        resStack.push(operStack.pop());
                    }
                    // 还需将item压入operStack栈
                    operStack.push(item);
                }
            } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时
                // 如果是左括号,则直接压入numStack
                if ("(".equals(item)) {
                    operStack.push(item);
                }
                // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃
                if (")".equals(item)) {
                    while (!"(".equals(operStack.peek())) {
                        resStack.push(operStack.pop());
                    }
                    // 此时operStack栈顶元素为(,将其弹出
                    operStack.pop();
                }
            } else { // 数字的话,直接压入resStack
                resStack.push(item);
            }
        }
        // step3:将numStack中剩余的运算符依次弹出并压入resStack
        while (!operStack.isEmpty()) {
            resStack.push(operStack.pop());
        }

        // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式
        ArrayList<String> list = new ArrayList<>();
        while (!resStack.isEmpty()) {
            list.add(resStack.pop());
        }
        Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式

        return list;
    }

    // 返回运算符的优先级,优先级是程序员来确定的,优先级使用数字表示
    // 数字越大,则优先级就越高
    // 假定目前只有 四种运算符: + - * /
    public static int priority(String oper) {
        if ("*".equals(oper) || "/".equals(oper)) {
            return 1;
        } else if ("+".equals(oper) || "-".equals(oper)) {
            return 0;
        } else {
            return -1;
        }
    }

    // 后缀表达式求值(逆波兰表达式求值)
    public static int evalRPN(ArrayList<String> list) {
        Stack<Integer> stack = new Stack<>();
        for (String item : list) {
            if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) {
                int num1 = stack.pop(); // 栈顶元素
                int num2 = stack.pop(); // 次顶元素
                switch (item) {
                    case "+" : stack.push(num1 + num2);break;
                    case "-" : stack.push(num2 - num1);break;
                    case "*" : stack.push(num1 * num2);break;
                    case "/" : stack.push(num2 / num1);break;
                }
            } else {
                stack.push(Integer.parseInt(item));
            }
        }
        return stack.pop();
    }
}

运行结果

中缀表达式:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
后缀表达式:[1, 2, 3, +, 4, *, +, 5, -]
后缀表达式的值为:16