数据结构—栈（中缀表达式求值）
文章目录
- 一、用栈求中缀表达式的值
-
- 1.1算法原理
- 1.2例题演示
- 二、用栈求后缀表达式的值
-
- 2.1算法原理
- 2.2例题演示
- 2.3C++代码
- 三、用栈求前缀表达式的值
-
- 3.1算法原理
- 3.2例题演示
一、用栈求中缀表达式的值
常见的表达式中含有操作数和运算符两种元素。常见的运算符又有括号，加减乘除等。已知运算优先级：1先算括号，2乘除，3加减。
1.1算法原理
算法的原理如下所示，一共需要2个栈，栈S1用来存放操作数，栈S2用来存放运算符。
可以用分支结构来判断，并做出相应的操作：
图中的计算的具体操作为：
- S1弹出的运算符op
- S2弹出两个操作数，先出栈的数=val2，放在op的右边；后出栈的数=val1，放在op的左边
- 计算val1 op val2的值，并将结果压入S1中。
另外还有需要注意的一点是：当cur<=top，将top出栈并计算后，当前运算符还没有处理完毕，必须回到运算符处再次判断，最终压入栈中，表明处理完毕，可以处理下一个字符。
1.2例题演示
例如有表达式：1 * 2 + 3 * ( 6 - 4 )，下列为关键步骤：
从前向后扫描：
扫描到1： 1入栈S1
扫描到乘号*：栈空，则乘号入栈S2
扫描到2： 2入栈S1
扫描到加号+：
1、比较栈顶top（乘号）和当前运算符（加号）的优先级。栈内的乘号优先，因此将乘号弹出，并将S1出栈两个元素，val2=先出栈的2，val1=后出栈的1。运算val1*val2=2，压入S1。
2、加号还没有处理完成，此时栈空，加号入栈
扫描到3： 3入栈S1
扫描到乘号*：比较栈顶符号（加号）与当前运算符（乘号）的优先级，当前运算符乘号优先，乘号入栈。
扫描到左括号(：左括号直接入栈S2
扫描到6： 6入栈S1
扫描到减号-：栈顶元素为左括号，减号直接入栈
扫描到4： 4入栈S1
扫描到右括号）：
1、将减号出栈，并从S1中弹出两个元素进行运算，val2=先出栈的4，val1=后出栈的6，计算val1-val2=2，将结果2压入S1。
2、栈顶为左括号，将左括号直接出栈。
此时表达式已全部扫描完成
处理栈内的剩余运算符，直接出栈并运算。
1、栈顶元素乘号出栈，并并从S1中弹出两个元素进行运算，val2=先出栈的2，val1=后出栈的3，计算val1*val2=6，将结果6压入S1。
2、栈顶元素加号出栈，并并从S1中弹出两个元素进行运算，val2=先出栈的6，val1=后出栈的2，计算val1+val2=8，将结果8压入S1。
3、S2为空
最终运算结果为S1的栈顶元素8。
二、用栈求后缀表达式的值
2.1算法原理
后缀表达式（逆波兰表达式）无需考虑运算符优先级，因为已经通过顺序明确了计算步骤，且其中不存在括号。
我们只需要用一个栈S，从前向后扫描表达式：
- 当遇到操作数，则入栈S。
- 当遇到运算符，则将操作数出栈S，并计算。
计算的具体操作与1.1一样：
- 当前扫描到的运算符op
- S弹出两个操作数，先出栈的数=val2，放在op的右边；后出栈的数=val1，放在op的左边
- 计算val1 op val2的值，并将结果压入S中。
最终表达式扫描完毕之后，栈的栈顶元素为最终结果。
2.2例题演示
例如有表达式：1 * 2 + 3 * ( 6 - 4 )，其后缀表达式为：1 2 * 3 6 4 - * +
从前向后扫描：
扫描到1： 1入栈
扫描到2： 2入栈
扫描到乘号*：从S中弹出两个元素进行运算，val2=先出栈的2，val1=后出栈的1，计算val1*val2=2，将结果2压入S。
扫描到3： 3入栈
扫描到6： 6入栈
扫描到4： 4入栈
扫描到减号-：从S中弹出两个元素进行运算，val2=先出栈的4，val1=后出栈的6，计算val1-val2=2，将结果2压入S。
扫描到乘号*：从S中弹出两个元素进行运算，val2=先出栈的2，val1=后出栈的3，计算val1*val2=6，将结果6压入S。
扫描到加号+：从S中弹出两个元素进行运算，val2=先出栈的6，val1=后出栈的2，计算val1+val2=8，将结果8压入S。
表达式扫描完毕，最终结果为S的栈顶元素8。
2.3C++代码
逆波兰式表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/?envType=problem-list-v2&envId=stack
class Solution {public: int evalRPN(vector<string>& tokens) { stack<int> st; for(int i=0;i<tokens.size();i++){ if(tokens[i]!=\"+\" && tokens[i]!=\"-\" && tokens[i]!=\"*\" && tokens[i]!=\"/\"){ st.push(stoi(tokens[i])); } else{ int val2=st.top(); st.pop(); int val1=st.top(); st.pop(); if(tokens[i]==\"+\") st.push(val1+val2); if(tokens[i]==\"-\") st.push(val1-val2); if(tokens[i]==\"*\") st.push(val1*val2); if(tokens[i]==\"/\") st.push(val1/val2); } } return st.top(); }};三、用栈求前缀表达式的值
3.1算法原理
求前缀表达式的值的算法与求后缀表达式的算法类似，主要区别有：
前缀表达式（波兰表达式）同样无需考虑运算符优先级，且其中也不存在括号。
我们只需要用一个栈S，从后向前扫描表达式：
- 当遇到操作数，则入栈S。
- 当遇到运算符，则将操作数出栈S，并计算。
计算的具体操作与2.1一样：
- 当前扫描到的运算符op
- S弹出两个操作数，先出栈的数=val1，放在op的左边；后出栈的数=val2，放在op的右边
- 计算val1 op val2的值，并将结果压入S中。
最终表达式扫描完毕之后，栈的栈顶元素为最终结果。
3.2例题演示
例如有表达式：1 * 2 + 3 * ( 6 - 4 )，其前缀表达式为：+ * 1 2 * 3 - 6 4
从后向前扫描：
扫描到4： 4入栈
扫描到6： 6入栈
扫描到减号-：从S中弹出两个元素进行运算，val1=先出栈的6，val2=后出栈的4，计算val1-val2=2，将结果2压入S。
扫描到3： 3入栈
扫描到乘号*：从S中弹出两个元素进行运算，val1=先出栈的3，val2=后出栈的2，计算val1*val2=6，将结果6压入S。
扫描到2： 2入栈
扫描到1： 1入栈
扫描到乘号*：从S中弹出两个元素进行运算，val1=先出栈的1，val2=后出栈的2，计算val1*val2=2，将结果2压入S。
扫描到加号+：从S中弹出两个元素进行运算，val1=先出栈的2，val2=后出栈的6，计算val1+val2=8，将结果8压入S。
表达式扫描完毕，最终结果为S的栈顶元素8。
