| 记录编号 |
155800 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
表达式转换 |
最终得分 |
100 |
| 用户昵称 |
 devil |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.190 s |
| 提交时间 |
2015-03-30 19:37:28 |
内存使用 |
6.04 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <cstring>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=300010;
const int MAX_INT=0x7fffffff;
const int MAXT=210;
char trees[MAXN*4];
string s;
int lrd[MAXN][2]; ///第二维的0表示是数字，1表示是符号
int next_lrd[MAXN][2]; ///同上
int len=0;
void build_tree(int l,int r,int dir)
{
if(l>r) return;
if(l==r) {trees[dir]=s[l];return;}
///if(s[l]=='('&&s[r]==')') {l++;r--;}
int lb=0,rb=0;bool flag=false;
///第一遍找'+'号或'-'号做根节点
for(int i=r;i>=l;i--)
{
if(s[i]=='(') lb++;
else if(s[i]==')') rb++;
if((s[i]=='+'||s[i]=='-')&&lb==rb)
{
trees[dir]=s[i];
build_tree(l,i-1,dir*2);
build_tree(i+1,r,dir*2+1);
flag=true;break;
}
}
///没有加号或减号就使用最后一个'*'号或'/'号做根节点
if(!flag)
{
for(int i=r;i>=l;i--)
{
if(s[i]=='(') lb++;
else if(s[i]==')') rb++;
else if((s[i]<'0'||s[i]>'9')&&lb==rb)
{
if(s[i]=='^') ///对乘方进行特殊处理
{
///if(s[i-1]!=')') continue;
if(i-l>2&&s[i-1]!=')') continue;
}
trees[dir]=s[i];
build_tree(l,i-1,dir*2);
build_tree(i+1,r,dir*2+1);
flag=true;break;
}
}
}
///在递归之后如果这一段表达式被一个括号整个括起来
if(!flag)
{
l++;r--; ///把最外面的括号去掉，剩下的步骤同上
if(l==r) {trees[dir]=s[l];return;}
for(int i=r;i>=l;i--)
{
if(s[i]=='(') lb++;
else if(s[i]==')') rb++;
if((s[i]=='+'||s[i]=='-')&&lb==rb)
{
trees[dir]=s[i];
build_tree(l,i-1,dir*2);
build_tree(i+1,r,dir*2+1);
flag=true;break;
}
}
if(!flag)
{
for(int i=r;i>=l;i--)
{
if(s[i]=='(') lb++;
else if(s[i]==')') rb++;
else if((s[i]<'0'||s[i]>'9')&&lb==rb)
{
if(s[i]=='^')
{
if(i-l>2&&s[i-1]!=')') continue;
}
trees[dir]=s[i];
build_tree(l,i-1,dir*2);
build_tree(i+1,r,dir*2+1);
flag=true;break;
}
}
}
}
}
void LRD(int dir)
{
if(trees[dir*2]==0&&trees[dir*2+1]==0)
{
lrd[len][0]=trees[dir]-'0';
lrd[len][1]=0;
len++;return;
}
LRD(dir*2);
LRD(dir*2+1);
if(trees[dir]>='0'&&trees[dir]<='9')
{
lrd[len][0]=trees[dir]-'0';
lrd[len][1]=0;
len++;
}
else
{
lrd[len][0]=trees[dir];
lrd[len][1]=1;
len++;
}
}
void cop(int len)
{
for(int i=0;i<len;i++)
{
lrd[i][0]=next_lrd[i][0];
lrd[i][1]=next_lrd[i][1];
}
}
int main()
{
///freopen("sample_data.in","r",stdin);
///freopen("data.in","r",stdin);
freopen("express.in","r",stdin);
freopen("express.out","w",stdout);
s.clear();
memset(lrd,0,sizeof(lrd));
cin>>s;
len=s.size();
build_tree(0,len-1,1); ///建立表达式树
///for(int i=0;i<151656;i++) if(trees[i]!=0) cout<<trees[i];
len=0;
LRD(1); ///求树的后序遍历
for(int i=0;i<len;i++)
{
if(lrd[i][1]==0) printf("%d ",lrd[i][0]);
else printf("%c ",lrd[i][0]);
}
printf("\n");
///按题目的做法进行计算
while(len>1)
{
int nlen=0;memset(next_lrd,0,sizeof(next_lrd));
bool flag=false;
for(int i=0;i<len;i++)
{
if(!flag&&lrd[i+2][1]==1)
{
if(lrd[i+2][0]=='+')
{
printf("%d",lrd[i][0]+lrd[i+1][0]);
next_lrd[nlen][0]=lrd[i][0]+lrd[i+1][0];
}
else if(lrd[i+2][0]=='-')
{
int t;
t=lrd[i][0]-lrd[i+1][0];
printf("%d",t);
next_lrd[nlen][0]=t;
}
else if(lrd[i+2][0]=='*')
{
printf("%d",lrd[i][0]*lrd[i+1][0]);
next_lrd[nlen][0]=lrd[i][0]*lrd[i+1][0];
}
else if(lrd[i+2][0]=='/')
{
printf("%d",(lrd[i][0])/(lrd[i+1][0]));
next_lrd[nlen][0]=(lrd[i][0])/(lrd[i+1][0]);
}
else if(lrd[i+2][0]=='^')
{
int t=pow((int)(lrd[i][0]),(int)(lrd[i+1][0]));
printf("%d",t);
next_lrd[nlen][0]=t;
}
next_lrd[nlen++][1]=0;
flag=true;i+=2;
}
else
{
if(lrd[i][1]==0) printf("%d",lrd[i][0]);
else printf("%c",lrd[i][0]);
next_lrd[nlen][0]=lrd[i][0];
next_lrd[nlen][1]=lrd[i][1];
nlen++;
}
printf(" ");
}
len=nlen;printf("\n");
memset(lrd,0,sizeof(lrd));
cop(nlen);
}
return 0;
}