中缀表达式计算中栈内优先级、栈外优先级的排序原理
前⾔：
有关中缀表达式计算是数据结构中⾮常经典的题⽬，以⾄于很多⽂章或课本喜欢直接给出计算⽅法⼀步到位，但关于其中的原理却并未深究，本⽂试图通过分析运算符的栈内优先级，栈外优先级的排序⽅法探求中缀表达式计算中的原理。 为了简便起见，在本⽂的讨论中只考虑双⽬运算符（仅＋、－、＊、/  四种）以及括号。并默认输⼊的表达式正确。
引⽤：
请看完这篇⽂章以对中缀表达式的计算有⼀个⼤体的了解 ：
正⽂：
中缀表达式的两种经典的计算⽅法，即转为后缀表达式法（间接法）与直接计算法。我们分别讨论这两种⽅法的优先级排序。
1.中缀转后缀表达式算法（间接法）
1.1需要什么样的数据结构？
⼀个运算符栈⽤来处理所有运算符，并将他们按正确的排序输出到后缀表达式中。
⼀个输出序列⽤来输出后缀表达式（可以⽤stack ，也可以⽤vector、string等 ，因为需要的操作只是在序列尾添加数据），可以记为操作数栈，因为遍历时遇到操作数直接压栈，但其中也会有运算符。
1.2运算规则是什么？
结合中缀表达式的计算规则及后缀表达式的计算规则：
中缀（⼈的计算）：
(1) 先计算括号内，后计算括号外；
(2) 在⽆括号或同层括号内，先乘除运算，后加减运算，即乘除运算的优先级⾼于加减运算的优先级；
(3) 同⼀优先级运算，从左向右依次进⾏。
后缀（计算机的计算）：
从左到右扫描后缀表达式，如果遇到操作数，将其压⼊栈中，如果遇到操作符，则从栈中弹出两个操作数，计算结果，然后把结果⼊栈，直到遍历完后缀表达式，则计算完成，此时的栈顶元素即为计算
结果。
1.3优先级排序及操作步骤？
这种情况的优先级排序⽐较简单也易于理解，只将四则运算的优先级编码，记 ＋、－为 0， 记 *  、 /  为1。
当遇到操作数的时候放⼊输出序列中。
当遇到运算符时情况变得复杂，由于运算符有不同的优先级，我们不能确定取到的运算符是否可以直接计算，需要和上⼀个操作符进⾏⽐较：如果优先级相等，说明是同⼀类型的运算符，应该从左到右进⾏运算，即先算栈顶运算符（出栈到输出队列），在把这个运算符压栈；如果该运算符优先级低，说明应该先进⾏栈内运算符的计算，直到该运算符⽐栈顶的⾼再压栈；如果该运算符优先级⾼，则直接压栈。可以看出，我们的运算符栈实际上是在维护⼀个严格递增的单调队列。
当遇到括号，如果左括号直接进栈，如果遇到右括号，需要依次取出栈中的运算符并输出，直到遇到左括号并弹出左括号（因为后缀表达式不存在括号）
遍历完之后将运算符栈依次弹出到输出序列
1.4代码⽰例
#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<locale>
using namespace std;
//判断是否为运算符
bool isops(string s) {
if (s == "+" || s == "-" || s == "*" || s == "/")  return true;
else
return false;
}
//定义运算符优先级
int icp(char c)
{
if (c == '*' || c == '/')
return 1;
if (c == '+' || c == '-')
return 0;
}
//中缀转后缀
vector <string> MidtoRPN(string s)
{
vector<string> out;
stack<string> sta;
string str = "";
int i = 0;
while (i < s.size())
{
//1.读⼊操作数
if (isdigit(s[i]))
{
str += s[i];
i++;
while (i < s.size() && isdigit(s[i]))
{
str += s[i];
i++;
}
sta.push(str);
str = "";
}
//2.读⼊开括号
else if (s[i] == '(')
{
str += s[i];
sta.push(str);
str = "";
运算符优先级按从高到低排列i++;
}
//3.读⼊闭括号
else if (s[i] == ')')
{
while (!pty() && p()[0] != '(')  {
out.push_p());
sta.pop();
}
sta.pop();//弹出左括号
sta.pop();//弹出左括号
i++;
}
//4.读⼊运算符
else
{
while (!pty() && p()[0] != '(' && icp(s[i]) <= p()[0]))  {
out.push_p());
sta.pop();
}
str += s[i];
sta.push(str);
str = "";
i++;
}
}
while (!pty())
{
out.push_p());
sta.pop();
}
return out;
}
//后缀表达式求值
double evalRPN(vector<string>& tokens)
{
double a, b;
stack<double> sta;
for (auto i : tokens)
{
if (!isops(i))
{
sta.push((double)stoi(i));
}
else
{
a = p();
sta.pop();
b = p();
sta.pop();
if (i == "+")
sta.push(a + b);
else if (i == "-")
sta.push(b - a);
else if (i == "*")
sta.push(a * b);
else if (i == "/")
{
if (a == 0)
{
cout << "除数不能为0" << endl;
exit(0);
}
sta.push(b / a);
}
}
}
p();
}
//中缀表达式间接求值
double calculate(string s)
{
vector<string> res = MidtoRPN(s);
vector<string> res = MidtoRPN(s);
return evalRPN(res);
}
int main()
{
double result = calculate("3*(7-2)");
cout << result << endl;
return 0;
}
2.中缀表达式直接求值
2.1与第⼀种⽅法思路有什么区别
⼤体思路相同，只是在第⼀种⽅法中，我们将从运算符栈中弹出的运算符输出到后置表达式中；⽽弹出的运算符不输出，⽽是从操作数栈取两个数直接进⾏运算，并把运算结果压⼊操作数栈。
2.2需要什么样的数据结构
⼀个操作数栈(nums)
⼀个运算符栈(ops)
2.3 运算符的优先级排序
该种⽅法下的优先级排序极为复杂，你可能看过下⾯这两种图
其实下⾯这张图就是按上⾯优先级的编码进⾏⽐较得到的图，可是为什么，为什么会是这样呢？
2.3.1什么是栈内优先级，什么是栈外优先级？
当遍历到⼀个运算符时，我们先不⼊栈，⽽将它的优先级与栈顶元素的优先级⽐较；当前遍历到的运算符在栈外，取栈外优先级，栈顶元素取栈内优先级，将这两种优先级进⾏⽐较。
2.3.2为什么要有栈内和栈外两种优先级，⼀种不⾏吗？
根据2.1的分析，这两种⽅法⼤体思路⼀样，直接求中缀表达式⽤⼀种优先级的排序是完全可以的，间接法也可以⽤栈内和栈外两种优先级算法。这两种⽅法使⽤时是等价的，⽽⼤家约定俗称的作法就是：转后缀表达式法⽤⼀种优先级排序，直接法⽤两种优先级排序，也许这就是经典8，咱也不太懂呢~
2.3.3两种优先级是怎么排的，意义是什么？
我们发现所有的⼆元运算符不管是在栈内还是栈外的优先级排序都是⼀样的：即乘⽅>乘除>加减。这与我们在前⽂的优先级排序相符，⽽这种双优先级排序的灵魂就在于将左括号 (  、右括号 ）及 #  进⾏了编码。下⾯为运算符进栈的⼏种情况的编码分析：
对于 # ：我们⽤这个符号标志着表达式的开始和结束，若计算 "3*(7-2)" ，转为计算 "#3*(7-2)#" ，⼀开始先在运算符栈中放⼊⼀个#, 再遇到⼀个#时，说明表达式已经结束，我们需要依次取出运算符栈中剩下的运算符进⾏运算，直到两个#相遇，程序结束，返回最终结果，因此，我们需要在遇到#时将栈中全部元素出栈，分析可知#的栈外优先级应该是最低的，编码为0；
对于  (  :  遇到左括号需要直接压栈，因此其栈外优先级应该⽐所有⼆元运算符的栈内优先级都⾼，编码为8；
对于  ）：遇到右括号，我们需要将左右括号之间的元素出栈，因此其栈外优先级应该⽐所有⼆元运算符的栈内优先级都低，编码为1；
当遇到左右括号相遇时，我们需要消除这⼀对括号，定义当栈外优先级和栈内优先级相等时消除，则左括号（ 的栈内优先级应该等于右括号  ） 的栈外优先级，为1。
对于所有的⼆元运算符： 宏观顺序是乘⽅>乘除>加减，⽽每⼀种类型的栈内外优先级都不相等，⽽是差1，这是因为当连续遇到两个同类型的运算符时，我们应该从左到右运算，即先算栈内的，再算栈外的，因此内⽐外要⾼。
可以看出，该运算符栈实际上也是在维护⼀个严格递增的单调队列。⽽通过将（ 、）、# 的编码，简
化了上⼀种算法中括号匹配和表达式遍历结束剩余运算符出栈的步骤，使其和其它⼆元运算符⼀样通过编码参与运算，消除其特殊性。
1.4操作步骤
依次读⼊表达式中的每个字符，若是
·操作数，则进nums栈；
·运算符s1，则和ops栈中的栈顶元素s2做⽐较再操作。
1）若icp(s1)>isp(s2)，则s1⼊栈，接收下⼀字符；
2）若icp(s1)==isp(s2)，则ops中的栈顶元素出栈，接收下⼀字符。
3）若icp(s1)<isp(s2)，则从nums栈顶弹出两个操作数，与ops中的栈顶元素做运算，并将运算结果⼊nums栈，并不接收下⼀字符，因为栈内可能有多个⽐该字符优先级⾼的运算符，要⼀直进⾏⼆元运算的操作直⾄转为1或2的情况；
直⾄表达式扫描完毕。
1.5代码⽰例
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
//栈内优先级
int isp(char ch)
{
switch (ch)
{
case '#': return 0;
case '(': return 1;
case '^':return 7;
case '*':case '/':case '%':return 5;
case '+':case '-':return 3;
case ')':return 8;
}
}
//栈外优先级
int icp(char ch)
{
switch (ch)
{
case '#': return 0;
case '(': return 8;
case '^':return 6;
case '*':case '/':case '%':return 4;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。