🌱本专栏将会从基础开始，循序渐进，每天刷一道算法题，也请大家多多支持。数据结构虽然难，但只要肯坚持，一定能学好，希望大家都能够从中获益。
📫专栏地址: 🍇每日一道算法题专栏 🍉数据结构专栏
📫本专栏的所有代码都将更新在Gitee上，项目地址：项目地址
📫相关数据结构演示软件:链接地址
📫数据结构在线演示地址：https://visualgo.net/zh https://algorithm-visualizer.org/

准备好了吗
Let’s go!

今天带来的算法是如何用栈把中序表达式转成逆序表达式，并通过栈计算逆序表达式的值，本文将详细讲解中缀表达式、后缀表达式是什么、以及如何写代码实现中缀转后缀和后缀表达式的计算。

1 栈在表达式求值中的应用

下图是我们所熟悉的算术表达式:

该算法表达式由三部分组成:操作数、运算符、界限符（界限符指括号，反映了计算的先后顺序）。忽然有一天，一位来自波兰的数学家有了一个这样的一个灵感:能否可以不用界限符也能无 歧义地表达运算顺序？然后就出现了波兰表达式(前缀表达式)和逆波兰表达式(后缀表达式)。接下来介绍一下中缀表达式、后缀表达式以及前缀表达式分别是什么东西:

1.1 中缀表达式

中缀表达式就是我们生活中常见的表达式，如下图所示：

1.2 后缀表达式

后缀表达式，又称逆波兰式，不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则），非常方便计算机的计算。

后缀表达式的计算过程如下：
1️⃣从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈
2️⃣重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

计算后缀表达式的动态流程如下,以1+2-3*2的后缀表达式为例:

另一个案例：
后缀表达式为“2 3 + 4 × 5 -”计算过程如下：
  1️⃣从左至右扫描，将 2 和 3 压入堆栈；
  2️⃣ 遇到 + 运算符，因此弹出 3 和 2（ 3 为栈顶元素，2 为次顶元素），计算出 3+2 的值，得 5，再将 5 入栈；
  3️⃣ 将 4 入栈；
  4️⃣接下来是 × 运算符，因此弹出 4 和 5，计算出 4 × 5 = 20，将 20 入栈；
  5️⃣将 5 入栈；
  6️⃣最后是-运算符，计算出 20-5 的值，即 15，由此得出最终结果

1.3 栈实现中缀表达式转后缀表达式

中缀转后缀的手算方法如下（考试时候会用到，这里不做具体讨论，主要讨论算法实现的步骤）：
1️⃣ 确定中缀表达式中各个运算符的运算顺序
2️⃣ 选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数
3️⃣ 如果还有运算符没被处理，就继续 2️⃣

用代码实现中缀表达式转后缀表达式算法实现的步骤如下：
  1️⃣初始化两个栈：运算符栈s1和储存中间结果的栈s2；
  2️⃣ 从左至右扫描中缀表达式；
  3️⃣ 遇到操作数时，将其压s2；
  4️⃣ 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
    1)：如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符压入s1；
    2)：否则，若优先级比栈顶运算符的高，也将运算符压入 s1;
    3)：否则，说明优先级小于等于栈顶运算符的优先级，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到4.1与s1中新的栈顶运算符相比较；
  5️⃣ 遇到括号时：
    1)：如果是左括号“(”，则直接压入 s1；
    2)：如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃；
  6️⃣ 重复步骤（2）至（5），直到表达式的最右边；
  7️⃣ 将 s1 中剩余的运算符依次弹出并压入 s2；
  8️⃣ 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：

表格的形式如下所示:

扫描到的元素	s2(栈底->栈顶)	s1 (栈底->栈顶)	说明
1	1	空	数字，直接入栈
+	1	+	s1为空，运算符直接入栈
(	1	+ (	左括号，直接入栈
(	1	+ ( (	同上
2	1 2	+ ( (	数字
+	1 2	+ ( ( +	s1栈顶为左括号，运算符直接入栈
3	1 2 3	+ ( ( +	数字
)	1 2 3 +	+ (	右括号，弹出运算符直至遇到左括号
×	1 2 3 +	+ ( ×	s1栈顶为左括号，运算符直接入栈
4	1 2 3 + 4	+ ( ×	数字
)	1 2 3 + 4 ×	+	右括号，弹出运算符直至遇到左括号
–	1 2 3 + 4 × +	–	-与+优先级相同，因此弹出+，再压入-
5	1 2 3 + 4 × + 5	–	数字
到达最右端	1 2 3 + 4 × + 5 –	空	s1中剩余的运算符

代码演示如下:

//中缀转后缀
public static String midTranstoBack(String str){
    LinkedStack<Character> s1 = new LinkedStack<Character>(); //栈s1,用于存储符号
    LinkedStack<Character> s2 = new LinkedStack<Character>(); //栈s2，用于存储数字
    HashMap<Character, Integer> characterHashMap = new HashMap<Character, Integer>();//用于存放优先级，数字越小，优先级越小
    characterHashMap.put('+',0);
    characterHashMap.put('-',0);
    characterHashMap.put('*',1);
    characterHashMap.put('/',1);
    characterHashMap.put('(',2);
    characterHashMap.put(')',2);
    for(int i=0;i<str.length();i++){
        char ch = str.charAt(i);
        //如果是数字,直接放到s2
        if(ch >= '0' && ch <= '9'){
            s2.push(ch);
        }
        else if(ch=='('){ //如果是左括号,直接压入s1
            s1.push(ch);
        }
        else if(ch==')'){ //如果是右括号,则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃
            char tmp = s1.pop();
            while(tmp != '('){
                s2.push(tmp);
                tmp = s1.pop();
            }
        }
        else {//否则为运算符
            {
                // 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符压入s1
                while (true){
                    if(s1.isEmpty() || s1.top() == '('){
                        s1.push(ch);
                        break;
                    }
                    //get是获取key对应的值,若优先级比栈顶运算符的高，将运算符压入s1
                    else if(characterHashMap.get(ch) > characterHashMap.get(s1.top())){
                        s1.push(ch);
                        break;
                    }
                    //若优先级小于等于栈顶运算符的高，将运算符压入s1
                    else {
                        s2.push(s1.pop());
                    }
                }
            }
        }
    }
    //将 s1 中剩余的运算符依次弹出并压入 s2
    while(!s1.isEmpty()){
        s2.push(s1.pop());
    }
    StringBuffer sb = new StringBuffer();
    //结果的逆序即为中缀表达式对应的后缀表达式
    while (!s2.isEmpty()){
        sb.insert(0,s2.pop());
    }
    return sb.toString();
}

关键部分如下图所示:

这里的栈采用的是自己实现的链式栈，没有使用系统的ArrayList，完整代码如下所示:

//链栈

// symbol match

import java.util.HashMap;
import java.util.Scanner;

//结点
class LinkedNode<T>{
    public T iData;         //数据域
    public LinkedNode<T> next;    //指向下一个结点

    public LinkedNode(T iData) {
        this.iData = iData;
        this.next = null;
    }

    public LinkedNode(T iData, LinkedNode<T> next) {
        this.iData = iData;
        this.next = next;
    }

    //输出用
    @Override
    public String toString() {
        return "LinkedNode{" +
                "iData=" + iData +
                ", next=" + next +
                '}';
    }
}
//链栈
class LinkedStack<T> {
    public LinkedNode<T> first; //链表的第一个结点

    //构造函数
    public void LinkList() {
        first = null;
    }

    //判断链栈是否为空
    public boolean isEmpty() {
        return first == null;
    }

    //push
    public void push(T data){
        LinkedNode newNode = new LinkedNode(data);
        newNode.next = first;
        first = newNode;
    }

    //pop
    public T pop(){
        if (first == null){
            System.out.println("链表为空");
            return null;
        }
        T front =  first.iData;
        first = first.next;
        return front;
    }

    //top 获得栈顶元素
    public T top(){
        if(first == null){
            return null;
        }
        return first.iData;
    }

}


public class _002LinkStackTest {
    
    //中缀转后缀
    public static String midTranstoBack(String str){
        LinkedStack<Character> s1 = new LinkedStack<Character>(); //栈s1,用于存储符号
        LinkedStack<Character> s2 = new LinkedStack<Character>(); //栈s2，用于存储数字
        HashMap<Character, Integer> characterHashMap = new HashMap<Character, Integer>();//用于存放优先级，数字越小，优先级越小
        characterHashMap.put('+',0);
        characterHashMap.put('-',0);
        characterHashMap.put('*',1);
        characterHashMap.put('/',1);
        characterHashMap.put('(',2);
        characterHashMap.put(')',2);
        for(int i=0;i<str.length();i++){
            char ch = str.charAt(i);
            //如果是数字,直接放到s2
            if(ch >= '0' && ch <= '9'){
                s2.push(ch);
            }
            else if(ch=='('){ //如果是左括号,直接压入s1
                s1.push(ch);
            }
            else if(ch==')'){ //如果是右括号,则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃
                char tmp = s1.pop();
                while(tmp != '('){
                    s2.push(tmp);
                    tmp = s1.pop();
                }
            }
            else {//否则为运算符
                {
                    // 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符压入s1
                    while (true){
                        if(s1.isEmpty() || s1.top() == '('){
                            s1.push(ch);
                            break;
                        }
                        //get是获取key对应的值,若优先级比栈顶运算符的高，将运算符压入s1
                        else if(characterHashMap.get(ch) > characterHashMap.get(s1.top())){
                            s1.push(ch);
                            break;
                        }
                        //若优先级小于等于栈顶运算符的高，将运算符压入s1
                        else {
                            s2.push(s1.pop());
                        }
                    }
                }
            }
        }
        //将 s1 中剩余的运算符依次弹出并压入 s2
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        StringBuffer sb = new StringBuffer();
        //结果的逆序即为中缀表达式对应的后缀表达式
        while (!s2.isEmpty()){
            sb.insert(0,s2.pop());
        }
        return sb.toString();
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();  //测试案例1+((2+3)*4)-5
        System.out.println(midTranstoBack(str));

    }
}

1.4 栈实现后缀表达式的计算

用栈实现后缀表达式的计算流程如下：

1️⃣从左往右扫描下一个元素，直到处理完所有元素

2️⃣若扫描到操作数则压入栈，并回到1️⃣；否则执行3️⃣

3️⃣若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1️⃣

计算后缀表达式的动态流程如下,以1+2-3*2的后缀表达式为例:

对应的代码如下:

public static int calcValue(String str){
    LinkedStack<Integer> s1 = new LinkedStack<Integer>();
    for(int i=0;i<str.length();i++){
        char ch = str.charAt(i);
        if(ch>='0' && ch<='9'){//如果是数字,入栈
            s1.push(ch - '0');
        }
        else {//否则为运算符
            int num1 = s1.pop();
            int num2 = s1.pop();
            //计算完后压栈
            if('+' == ch){
                s1.push(num2+num1);
            }
            else if('-' == ch){
                s1.push(num2-num1);
            }
            else if('*' == ch){
                s1.push(num2*num1);
            }
            else if('/' == ch){
                s1.push(num2/num1);
            }
        }
    }
    //栈顶元素即为计算的结果
    return s1.top();
}

测试结果如下:

完整代码如下:

//链栈

// symbol match

import java.util.HashMap;
import java.util.Scanner;

//结点
class LinkedNode<T>{
    public T iData;         //数据域
    public LinkedNode<T> next;    //指向下一个结点

    public LinkedNode(T iData) {
        this.iData = iData;
        this.next = null;
    }

    public LinkedNode(T iData, LinkedNode<T> next) {
        this.iData = iData;
        this.next = next;
    }

    //输出用
    @Override
    public String toString() {
        return "LinkedNode{" +
                "iData=" + iData +
                ", next=" + next +
                '}';
    }
}
//链栈
class LinkedStack<T> {
    public LinkedNode<T> first; //链表的第一个结点

    //构造函数
    public void LinkList() {
        first = null;
    }

    //判断链栈是否为空
    public boolean isEmpty() {
        return first == null;
    }

    //push
    public void push(T data){
        LinkedNode newNode = new LinkedNode(data);
        newNode.next = first;
        first = newNode;
    }

    //pop
    public T pop(){
        if (first == null){
            System.out.println("链表为空");
            return null;
        }
        T front =  first.iData;
        first = first.next;
        return front;
    }

    //top 获得栈顶元素
    public T top(){
        if(first == null){
            return null;
        }
        return first.iData;
    }

}


public class _002LinkStackTest {
    // 括号匹配
    public static boolean bracketCheck(String str){
        LinkedStack<Character> S = new LinkedStack<Character>(); //初始化一个栈
        for(int i=0;i<str.length();i++){
            //如果扫描到左括号，则入栈
            if(str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{' ){
                S.push(str.charAt(i));
            }else{
                //扫描到右括号，且当前栈空
                if(S.isEmpty()){
                    return false;
                }
                //栈顶元素出栈
                char topElem = S.pop();
                //判断是否匹配
                if(str.charAt(i) == ')' && topElem != '('){
                    return false;
                }
                if(str.charAt(i) == ']' && topElem != '['){
                    return false;
                }
                if(str.charAt(i) == '}' && topElem != '{'){
                    return false;
                }
            }
        }
        //检索完全部括号后，栈空说明匹配成功
        return S.isEmpty();
    }

    //中缀转后缀
    public static String midTranstoBack(String str){
        LinkedStack<Character> s1 = new LinkedStack<Character>(); //栈s1,用于存储符号
        LinkedStack<Character> s2 = new LinkedStack<Character>(); //栈s2，用于存储数字
        HashMap<Character, Integer> characterHashMap = new HashMap<Character, Integer>();//用于存放优先级，数字越小，优先级越小
        characterHashMap.put('+',0);
        characterHashMap.put('-',0);
        characterHashMap.put('*',1);
        characterHashMap.put('/',1);
        characterHashMap.put('(',2);
        characterHashMap.put(')',2);
        for(int i=0;i<str.length();i++){
            char ch = str.charAt(i);
            //如果是数字,直接放到s2
            if(ch >= '0' && ch <= '9'){
                s2.push(ch);
            }
            else if(ch=='('){ //如果是左括号,直接压入s1
                s1.push(ch);
            }
            else if(ch==')'){ //如果是右括号,则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃
                char tmp = s1.pop();
                while(tmp != '('){
                    s2.push(tmp);
                    tmp = s1.pop();
                }
            }
            else {//否则为运算符
                {
                    // 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符压入s1
                    while (true){
                        if(s1.isEmpty() || s1.top() == '('){
                            s1.push(ch);
                            break;
                        }
                        //get是获取key对应的值,若优先级比栈顶运算符的高，将运算符压入s1
                        else if(characterHashMap.get(ch) > characterHashMap.get(s1.top())){
                            s1.push(ch);
                            break;
                        }
                        //若优先级小于等于栈顶运算符的高，将运算符压入s1
                        else {
                            s2.push(s1.pop());
                        }
                    }
                }
            }
        }
        //将 s1 中剩余的运算符依次弹出并压入 s2
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        StringBuffer sb = new StringBuffer();
        //结果的逆序即为中缀表达式对应的后缀表达式
        while (!s2.isEmpty()){
            sb.insert(0,s2.pop());
        }
        return sb.toString();
    }

    public static int calcValue(String str){
        LinkedStack<Integer> s1 = new LinkedStack<Integer>();
        for(int i=0;i<str.length();i++){
            char ch = str.charAt(i);
            if(ch>='0' && ch<='9'){//如果是数字,入栈
                s1.push(ch - '0');
            }
            else {//否则为运算符
                int num1 = s1.pop();
                int num2 = s1.pop();
                if('+' == ch){
                    s1.push(num2+num1);
                }
                else if('-' == ch){
                    s1.push(num2-num1);
                }
                else if('*' == ch){
                    s1.push(num2*num1);
                }
                else if('/' == ch){
                    s1.push(num2/num1);
                }
            }
        }
        return s1.top();
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();  //测试案例1+((2+3)*4)-5,1+2-3*2
        String backStr = midTranstoBack(str);
        System.out.println(backStr);
        System.out.println(calcValue(backStr));


    }
}