【每天一道算法题】栈的应用：将中缀表达式转为后缀表达式以及后缀表达式求值(附动图，源码，讲解最详细，没有之一)

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

准备好了吗
Let’s go!

文章目录

• • 1 栈在表达式求值中的应用
  • • 1.1 中缀表达式
    • 1.2 后缀表达式
    • 1.3 栈实现中缀表达式转后缀表达式
    • 1.4 栈实现后缀表达式的计算

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

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

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

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

1.1 中缀表达式

中缀转后缀的手算方法：

1️⃣ 确定中缀表达式中各个运算符的运算顺序

2️⃣ 选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数

3️⃣ 如果还有运算符没被处理，就继续 2️⃣

1.2 后缀表达式

后缀表达式计算与前缀表达式类似，只是顺序是从左至右，具体过程如下：

1️⃣从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈

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️⃣初始化两个栈：运算符栈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”转换为后缀表达式的过程如下：

表格的形式如下所示:

代码演示如下:

//中缀转后缀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 matchimport 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 matchimport 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));    }}