题解 P1175 【表达式的转换】
NeosKnight · · 题解
全真模拟AC 不要问我怎么有毅力这样做出来 （至今为止我写过的最长的代码就这题了）
1.中转后 数字直接输出 每在表达式中插入一个算符就输出他（记得加空格） 最后记得栈中算符全部出栈并依次输出
2.预先计算出需要运算的次数（即算符个数）
3.从前往后扫 扫到一个算符就从他前面找两个数运算并将找过的位置置为空，再将得出的结果写回去（这里比较复杂，具体看代码）
然后输出；（还要注意负数的处理，我写的也很麻烦）
4.继续从原来的位置扫描，重复操作；
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
char sz[100001];
char hz[100001];
char stack[100001];
int top=0;
inline int doit(int x,int y,char how);
inline bool cmp(char ch,char cr)
{
if(ch==')'&&cr!='(') return 0;//右括号在没有遇到左括号时优先度最低；
else if(ch==')'&&cr=='(') return 1;//为括号的情况优先考虑 （两括号相遇要删除）
if(cr=='(') return 1;//在没有找到右括号之前左括号不能动；
if(ch=='+'||ch=='-') return 0;//加减法优先度一定不比之前的任何算符高；
if(ch=='^') return 1;
if(cr=='^') return 0;//'^'在所有除括号外的算符中优先度最高;
if((ch=='*'||ch=='/'||ch=='^')&&(cr=='+'||cr=='-')) return 1;//剩下的就只有当 ch （要入栈的算符）为乘除时 cr 为加减时 ch 优先度才比cr（top指向的算符）高
return 0;
}
void push(char ch,int &l)
{
if(ch=='(')
{
stack[++top]=ch;
}
else {
while(!cmp(ch,stack[top])&&stack[top]!='@')//未成功匹配到合适位置且未到栈底则top减1出栈
{
if(stack[top]!='('&&stack[top]!=')')
{hz[++l]=stack[top];cout<<stack[top]<<" ";}//每从栈中取出一个算符 就要输出（也可以最后再扫一遍，这样可能更方便）
top--;
}
stack[++top]=ch;//找到合适的位置放置运算符
if(stack[top]==')'&&stack[top-1]=='(')
top-=2;//抵消；
}
}
int main()
{
scanf("%s",sz);
stack[top]='@';
int len=strlen(sz);int j=0;
//hz[++j]='.';hz[++j]='.';hz[++j]='.';//防止出错多加几个空格
for(int i=0;i<len;i++)
{
if(sz[i]>='0'&&sz[i]<='9')
{
hz[j]=sz[i];cout<<sz[i]<<" ";
}
else if(sz[i]=='-'||sz[i]=='+'||sz[i]=='*'||sz[i]=='^'||sz[i]=='/')
{
hz[j]='.';//标记 (后缀表达式中)
hz[++j]='.';
hz[++j]='.';hz[++j]='.';
push(sz[i],j);
}
else if(sz[i]=='('||sz[i]==')')//括号不输出
{
hz[j]='.';
hz[++j]='.';
hz[++j]='.';hz[++j]='.';//多放几个空格
push(sz[i],j);
}
j++;
}
while(top!=0){
if(stack[top]!='('&&stack[top]!=')')
{hz[j++]=stack[top];cout<<stack[top]<<" ";}//输出算符
top--;//剩余算符全部出栈
}
top=0;len=strlen(hz);
int tot=0;
for(int i=0;i<len;i++) {
if(hz[i]=='+'||hz[i]=='*'||hz[i]=='-'||hz[i]=='^'||hz[i]=='/') tot++;//计算算符个数，确定计算次数；
}
int head=0;j=0;
cout<<endl;
while(tot)
{
tot--;
for(;head<len;head++)//头指针，指向算符，进行运算 (注意不要初始化，之后可以接着用)
{
if(hz[head]=='+'||hz[head]=='*'||hz[head]=='-'||hz[head]=='^'||hz[head]=='/')
{
int a=0,b=0;//寻找两个运算数
int p=head-1;while(hz[p]=='.') p--;//找到第一个数字
int l=1;//存储一个数有多少位；
while(233&&p>=0)
{
if(hz[p]=='.') break;//找到了退出
if(hz[p]=='-')
{a=-a;hz[p]='.';p--;break;}
a+=(hz[p]-'0')*l;
l*=10;
hz[p]='.';//使用过的标为空（就不往前挪了，浪费时间，也没必要）
p--;
}
l=1;
while(hz[p]=='.') p--;//找第二个数；
while(233&&p>=0)
{
if(hz[p]=='.') break;
if(hz[p]=='-')
{b=-b;hz[p]='.';p--;break;}
b+=(hz[p]-'0')*l;l*=10;
hz[p]='.';
p--;
}
int ans=doit(b,a,hz[head]);//后找到的数要放在前面！（因为是从后往前扫）
hz[head]='.';//标为空
if(tot==0)
{
cout<<ans<<endl;return 0;
}
for(int q=0;q<len;q++)
{
if(q==head) {cout<<ans<<" ";continue;}
if(hz[q]=='.') continue;
if(hz[q]=='-'&&q<=head) {
cout<<"-";continue;
}
if(hz[q]>='0'&&hz[q]<='9')
{
while(hz[q]>='0'&&hz[q]<='9'&&q<len)
{
cout<<hz[q];
q++;
}
cout<<" ";
q--;//for会加上去；
}
else cout<<hz[q]<<" ";
}
cout<<endl;/*把数给填上去*****/
bool fu=false;if(ans<0) {fu=true;ans*=-1;}
if(ans==0){
hz[head-1]='0';
}
else
{
int q;
for(q=head-1;hz[q-1]=='.'&&ans!=0;q--)
{
hz[q]=ans%10+'0';
ans/=10;
}
if(fu==true){
hz[q]='-';
}
}
break;
}
}
}
}
inline int doit(int x,int y,char how)//运算
{
int sum=0;
switch(how)
{
case '*':
sum=x*y;return sum;
case '-':
sum=x-y;return sum;
case '+':
sum=x+y;return sum;
case '/':
sum=x/y;return sum;
case '^':
sum=1;
for(int i=1;i<=y;i++)
{
sum*=x;
}
return sum;
default: return 0;
}
}