如下是求解后缀表达式8571-*+82/-的代码 。
Tips：此后缀表达式对应的中缀表达式是：8+5*(7-1)-8/2
#include <iostream>#include <stack>using namespace std;int main() { char exp[20]="8571-*+82/-"; stack<int> expStack; int num1; int num2; char opt; int res; for(int i=0; exp[i]!='\0'; i++) {if (exp[i]>='0' && exp[i]<='9') {//入栈expStack.push(exp[i]-'0');} else {//出栈num1=expStack.top();expStack.pop();//出栈num2=expStack.top();expStack.pop();//运算符opt=exp[i];switch(opt) {case '+':res=num2+num1;break;case '-':res=num2-num1;break;case '*':res=num2*num1;break;case '/':res=num2/num1;break;}expStack.push(res);} } cout<<expStack.top()<<endl; return 0;}执行后的输出结果：344. 中缀转后缀表达式虽然后缀表达式的计算过程要比中缀表达式简单很多，前提条件是要先把中缀表达式转换成后缀表达式 。转换流程：
- 初始化一个运算符栈 。
- 自左向右扫描中缀表达式，当扫描到操作数时直接连接到后缀表达式上 。
- 当扫描到操作符时 ， 和运算符栈栈顶的操作符进行比较 。如果比栈顶运算符高，则入栈 。如果比栈顶运算符低 ， 则把栈顶的运算符出栈后连接到中缀表达式上 。
- 若运算符是右括号，栈顶是左括号时，删除栈顶运算符（清除括号 。后缀表达式中是没有括号的，操作数后面的运算符的优先级由左向右降低） 。
- 重复以上过程直到遇到结束符 。
文章插图
4.1 流程演示如下把
8+5*(7-1)-8/2 中缀表达式转换成后缀表达式 。- 初始化运算符栈 。
文章插图
- 扫描中缀表达式，字符
8直接输出 ，+是第一个操作数，因可能后续有更高的运算符，入栈 。
文章插图
- 字符
5直接输出 ，*优先级大于栈顶+优先级，入栈 。
文章插图
(运算符在栈外优先级最高，入栈 。
文章插图
- 字符
7直接输出 ， 因(运算符在栈内优先级最低，-运算符入栈 。
文章插图
- 字符
1直接输出 ，)栈外优先级最低 。运算符出栈，一直碰到(。
文章插图
-运算符小于栈中的+、+运算符 。*、+运算符出栈 。-入栈 。
文章插图
/优先级大于-，入栈 。字符直接输出 。
文章插图
- 字符扫描结束，把运算符栈中的运算符全部出栈 。
文章插图
4.2 编码实现中缀表达式转后缀表达式的实现过程类似于中缀表达式的求值过程，只是不需要进行计算 。或者说中缀表达式的求值过程包括了中缀表达式转换成后缀表达式以及对后缀表达式求值过程 。
#include <iostream>#include <stack>#include <map>#include <cmath>#include <cstring>using namespace std;struct Opt { //运算符名字 char name; //栈内级别 int stackInJb; //栈外级别 int stackOutJb; Opt(char name,int in,int out) {this->name=name;this->stackInJb=in;this->stackOutJb=out; } /* *栈外运算符和栈内运算比较 */ bool compare(Opt* opt) {return this->stackOutJb > opt->stackInJb; } //显示 void desc() {cout<<this->name<<"-"<<this->stackInJb<<"-"<<this->stackOutJb<<endl; }};map<char,Opt*> maps;void mapOpt() { maps['^']=new Opt('^',3,4); maps['*']=new Opt('*',2,2); maps['/']=new Opt('/',2,2); maps['+']=new Opt('+',1,1); maps['-']=new Opt('-',1,1); maps['(']=new Opt('(',0,4); maps[')']=new Opt(')',-1,-1);}int main(int argc, char** argv) { mapOpt(); //后缀表达式 char hzExp[20]={'\0'}; int j=0; stack<char> optStack; //中缀表达式 char exps[20]="(8+5*(7-1)-8/2)"; optStack.push(exps[0]); //栈内运算符 Opt* opt; //栈外运算符 Opt* opt_; for(int i=1; exps[i]!='\0' ; ) {if( !(exps[i]>='0' && exps[i]<='9')) {//栈内最初是 ) 运算符opt=maps[optStack.top()];//栈外运算符opt_=maps[exps[i]];if(opt_->name==')' && opt->name=='(') {//子表达式结束optStack.pop();i++;continue;}//比较bool com=opt_->compare(opt);if (com) {//入栈optStack.push(opt_->name);i++;} else{//运算char n=opt->name;optStack.pop();hzExp[j]=n;j++;}} else {//数字字符hzExp[j]=exps[i];j++;i++;} } //hzExp[j]='\0'; cout<<hzExp<<endl; return 0;}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 分布式存储系统之Ceph集群启用Dashboard及使用Prometheus监控Ceph
- 1 Python全栈工程师之从网页搭建入门到Flask全栈项目实战 - ES6标准入门和Flex布局
- 使用Pytorch进行多卡训练
- AVX图像算法优化系列二: 使用AVX2指令集加速查表算法。
- <三>从编译器角度理解C++代码编译和链接原理
- springboot 多线程的使用
- windows C++ 异常调用栈简析
- 指南针使用的方法（大自然指南针有哪些)
- AspNetCore中 使用 Grpc 简单Demo
- 分布式存储系统之Ceph集群RadosGW基础使用
