🏆今日学习目标：
🍀例题讲解P1175 表达式的转换
✅创作者：贤鱼
⏰预计时间：25分钟
🎉个人主页：贤鱼的个人主页
🔥专栏系列：c++
🍁贤鱼的个人社区，欢迎你的加入 贤鱼摆烂团

P1175 表达式的转换

• 表达式的转换
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 样例 #2
  • • 样例输入 #2
    • 样例输出 #2
  • 提示
• 思路
• AC代码

表达式的转换

题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8-(3+2*6)/5+4 可以写为：8 3 2 6 * + 5 / - 4 +

其计算步骤为：

8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

输入格式

就一行，是一个中缀表达式。输入的符号中只有这些基本符号 0123456789+-*/^()，并且不会出现形如 2*-3 的格式。

表达式中的基本数字也都是一位的，不会出现形如 12 形式的数字。

所输入的字符串不要判错。

输出格式

若干个后缀表达式，第 i+1i + 1i+1 行比第 iii 行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

样例 #1

样例输入 #1

8-(3+2*6)/5+4

样例输出 #1

8 3 2 6 * + 5 / - 4 + 
8 3 12 + 5 / - 4 + 
8 15 5 / - 4 + 
8 3 - 4 + 
5 4 + 
9

样例 #2

样例输入 #2

2^2^3

样例输出 #2

2 2 3 ^ ^
2 8 ^
256

提示

运算的结果可能为负数，/ 以整除运算。并且中间每一步都不会超过 2312^{31}231。字符串长度不超过 100100100。

注意乘方运算 ^ 是从右向左结合的，即 2 ^ 2 ^ 3 为 2 ^ (2 ^ 3)，后缀表达式为 2 2 3 ^ ^。

其他同优先级的运算是从左向右结合的，即 4 / 2 / 2 * 2 为 ((4 / 2) / 2) * 2，后缀表达式为 4 2 / 2 / 2 *。

保证不会出现计算乘方时幂次为负数的情况，故保证一切中间结果为整数。

思路

我们首先来拆分一下题目

• 中缀表达式转换后缀表达式
• 后缀表达式逐步计算输出过程

我们来一步步解决问题
首先来处理一下中缀表达式转换
这里我们将问题继续细分
转换主要有一下几个问题

• +=/*按照什么顺序转换
• 如何处理^
• 如何处理()

众所周知，+=*/涉及一个先后顺序的问题，也就是优先度
先乘除后加减这是小学必备敲门砖
首先写一个函数处理一下顺序问题

int pd(char t){switch(t){case '+':return 1;case '-':return 1;case '*':return 2;case '/':return 2;case '^':return 3;case '(':return 0;case ')':return 0;default:return -1;}
}

没毛病吧

从现在开始，我们默认+ -是1，*/是2

用一个op栈存一下符号，记得保证符号的顺序上升
同时遇到左括号入栈，遇到右括号输出左右括号内部符号
遇到数字直接输出就好了

8-(3+2*6)/5+4-----8 3 2 6 * + 5 / - 4 +
通过讲解一下例题解释为什么上升以及括号问题
首先入栈-
接着入栈(+*
然后入栈)
这时候输出括号内的内容，顺序应该是*+（栈内先进后出）8 3 2 6 * +get
此时栈内还有一个-，接着入栈/
注意这时候入栈了一个+，所以输出/-
最后结束的时候判断一下op，有东西全部输出就好了

因为先乘除后加减，如果此时入栈了一个*接着入栈了一个+，因为 * 在+前面运算，所以我们要弹出*，
注意！！！直到弹出到比+优先度小的符号停止弹出，
为什么等于也要弹出？
咱俩优先度一样你在前头你先走

^就是个搅屎棍，需要单独处理
也很简单，题目中说了乘方运算从右向左结合，所以我们判断优先度的时候判断下，如果栈顶和输入元素都是^，直接break，和后面的内容说再见（反正从右往左咱俩都不走等到遇到比咱小的符号一起走）

整完了吧，处理一手运算问题
我们在上一个部分输出的时候记录一个栈ls，用来储存输出第一行的结果(注意此时是倒序，第一部分结束以后我们用一个fh栈来储存结果正序)
怎么运算？
遇到数字输出到num栈，遇到符号弹出num栈栈顶元素*2进行运算，运算完入栈输出就好,完事了
确实就是这么简单，写一个运算函数就好

int js(int x,int y,char t){switch(t){case '+':return x+y;case '-':return x-y;case '*':return x*y;case '/':return x/y;case '^':return pow(x,y);default:return -0x3f3f3f3f;//到不了这里不用管他}
}

注意输出的时候注意一下输出顺序
比如我们的num栈在一波操作下应该是数字的倒叙，输出的话需要反过来输出
fh栈相当于剩下的没有处理的部分，直接输出就好了，我们这里直接输出，记录一下然后再反过来塞回去，这个不慌看代码就懂了
然后继续重复上述操作，直到fh栈为空，这里num还剩一个，刚好输出答案
结束了，休息休息

AC代码

#include
#include
#include
#include
#include
using namespace std;
stackda,op;
char a;
int js(int x,int y,char t){switch(t){case '+':return x+y;case '-':return x-y;case '*':return x*y;case '/':return x/y;case '^':return pow(x,y);default:return -0x3f3f3f3f;}
}
int pd(char t){switch(t){case '+':return 1;case '-':return 1;case '*':return 2;case '/':return 2;case '^':return 3;case '(':return 0;case ')':return 0;default:return -1;}
}
stackfh;
stacknm;
stackls;
int wc;
void work(){while(cin>>a){if(isdigit(a)){da.push(a);char cc=da.top();ls.push(cc);cout<if(pd(a)==0){if(a=='(') op.push(a);else{while(!op.empty()&&op.top()!='('){cout<=1&&pd(a)<=3){if(!op.empty()){while(!op.empty()&&pd(a)<=pd(op.top())){if(pd(op.top())==pd(a)&&pd(a)==3) break;cout<ls.push(op.top());cout<num;
char t;
void cal(){while(!fh.empty()){t=fh.top();fh.pop();if(isdigit(t)){num.push(t-'0');}else{int x=num.top();num.pop();int b=num.top();num.pop();int sz=js(b,x,t);num.push(sz);while(!num.empty()){//反过来nm.push(num.top());num.pop();}while(!nm.empty()){//反过来cout<//反过来cout<//反过来fh.push(op.top());op.pop();}cout<work();while(!ls.empty()){//反过来fh.push(ls.top());ls.pop();}cout<