C++数据结构与STL--栈的应用--中缀表达式转后缀表达式

逃离我推掉我的手 2021-12-13 01:13 349阅读 0赞

**1.输入优先等级和栈优先等级定义：目的，解决右结合表达式问题，例如2^2^2为右结合表达式**  
  
![Center][]  
  
  
  
  
  
  
**2.累计等级与无效表达式分析：**  
  
![Center 1][]  
  
  
  
**3.使用栈处理相同或较低优先级的运算符  
Example:a\*b/c+d**

![Center 2][]

**4.处理右结合表达式运算符^  
Example:a^b^c**

![Center 3][]

**5.处理子表达式的左右圆括号。  
Example:处理a\*(b+c)中的子表达式（b+c)**

![Center 4][]

**实现代码：并未包含异常处理  
//操作符优先级类  
\#ifndef op\_priority\_H  
\#define op\_priority\_H  
  
  
class op\_priority  
\{  
private:  
int inputPriority; //输入优先级   
int stackPriority; //栈优先级  
char op; //运算操作符   
public:  
op\_priority()  
\{   
\}  
  
op\_priority( char ch):op(ch) //设置运算符的优先级   
\{   
switch(ch)  
\{   
case '+':  
case '-':  
 inputPriority=1;  
 stackPriority=1;  
 break;  
 case '\*':  
case '/':  
case '%':  
 inputPriority=2;  
 stackPriority=2;   
 break;  
case '^':   
 inputPriority=4;  
 stackPriority=3;   
 break;  
case '(':   
 inputPriority=5;  
 stackPriority=-1;   
 break;  
case ')':   
 inputPriority=0;  
 stackPriority=0;   
 break;  
  
\}  
\}  
  
char getOperator() //返回运算符   
 \{   
return op;  
\}  
  
friend bool operator>=(op\_priority &input,op\_priority &stack);  
  
\};  
  
  
  
  
bool operator>=(op\_priority &left,op\_priority &right)  
\{   
return left.stackPriority>=right.inputPriority;  
\}   
  
  
  
  
  
  
\#endif**

**//中缀转后缀类**

**\#ifndef in\_post\_convert\_H  
\#define in\_post\_convert\_H  
\#include<string>  
\#include<stack>  
\#include"op\_priority.h"  
using std::string;  
using std::stack;  
class in\_post\_convert  
\{  
private:  
string inExpr; //中缀表达式   
string postExpr; //后缀表达式   
stack<op\_priority> opStack;//操作符栈   
bool isDigt(char c) //判断字符是否为数字   
 \{   
return c>='0'&&c<='9';  
 \}  
  
 bool isOperator(char c) //判断字符是否为操作符  
\{   
 return c=='+'||c=='-'||c=='\*'||  
 c=='/'||c=='%'||c=='^';  
 \}  
  
 void popHeigherEqual(op\_priority op)   
 \{   
op\_priority tem;  
while(!opStack.empty()&&(tem=opStack.top())>=op) //把所有栈操作符的优先级大于输入优先级的操作符出栈   
\{   
postExpr+=tem.getOperator();  
 opStack.pop();  
\}  
 \}  
 public:  
 in\_post\_convert(string exp):inExpr(exp) //构造函数，初始化中缀表达式   
 \{   
 \}  
  
  
  
  
 string post() //把中缀表达式转换成后缀表达式  
\{   
for(int i=0;i<inExpr.length();i++) //从左往右扫描中缀表达式  
\{   
char ch=inExpr\[i\];  
if(isDigt(ch)) //如果是数字，直接写入后缀表达式   
\{   
postExpr+=ch;  
\}   
else if(isOperator(ch)||ch=='(') //处理操作符和'('  
\{   
op\_priority op(ch);  
popHeigherEqual(op); //把符合要求的操作符出栈   
opStack.push(op);  //把当前操作符进栈  
  
\}   
else if(ch==')') //处理')'  
\{   
op\_priority op(ch);  
popHeigherEqual(op); //把符合要求的操作符出栈   
opStack.pop(); //'('出栈   
\}   
\}   
  
while(!opStack.empty()) //把剩余操作符出栈   
\{   
op\_priority tem=opStack.top();  
postExpr+=tem.getOperator();  
opStack.pop();  
\}  
  
return postExpr;   
\}   
\};  
  
  
\#endif  
  
  
  
  
  
  
  
  
测试程序：  
\#include<iostream>  
\#include"in\_post\_convert.h"  
  
  
using std::cout;  
using std::endl;  
  
  
int main()  
\{  
string res;  
in\_post\_convert expr(string("3\*(4-2^5)+6"));  
res=expr.post();  
cout<<res<<endl; //3425^-\*6+  
  
\}  
  
  
  
  
  
运行解析：**  
![Center 5][]  
  
  
  
  
  
  
![Center 6][]

[Center]: /images/20211210/41b43ba2a6454ee399cf6af6278174db.png
[Center 1]: /images/20211210/afa37d5c9d304e4d8921dedaf4cc3702.png
[Center 2]: /images/20211210/37fe5c96234547bab92a1627adaa0606.png
[Center 3]: /images/20211210/ad479e5eb77a43ce8ff636c1c6c220fd.png
[Center 4]: /images/20211210/118424ff61d34344a5845d9ee2e1ee9c.png
[Center 5]: /images/20211210/d968cb2de0fd4d42b8588c0efcb6ad02.png
[Center 6]: /images/20211210/9e91c91ea74b462cb93486723e1dd1b3.png