codeforces gym 100357 K (表达式 模拟)
2024-08-30 23:42:22
题目大意
将一个含有+,-,^,()的表达式按照运算顺序转换成树状的形式。
解题分析
用递归的方式来处理表达式,首先直接去掉两边的括号(如果不止一对全部去光),然后找出不在括号内且优先级最低的符号。如果优先级相同,则如果是左结合性(+,-,*,/)则选择最右边的一个,如果是右结合性(^)则选择最最左边的一个。
主要恶心的地方在于输出上。主要是记录一下每个点和符号的位置,在递归和返回时传递一些参数。
ps:虽然输出比较恶心,但最终实现出来后还是感到十分地身心愉悦。
参考程序
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
string s;
int a[];
int level(char ch)
{
switch (ch)
{
case '+':;
case '-':return ;
case '*':;
case '/':return ;
case '^':return ;
default:return ;
}
} int r,c,tmp=; struct node{
int l,mid,r,len;
char ch;
}w[]; pii solve(int x,int y,int heap,int op)
{
//cout<<s.substr(x,y-x+1)<<endl;
if (heap>r) r=heap;
if (op>c) c=op;
while (s[x]=='(' && s[y]==')')
{
int t=,flag=;
for (int i=x+;i<=y-;i++)
{
if (s[i]=='(') t++; else if (s[i]==')') t--;
if (t<) flag=;
}
if (flag)
{
x++;
y--;
}
else break;
}
int len=y-x+;
if (len==)
{
w[++tmp]=(node){op,op,op,heap,s[x]};
return pii(,);
}
for (int i=x;i<=y;i++) a[i]=;
if (s[x]=='(') a[x]=; else a[x]=;
for (int i=x+;i<=y;i++)
if (s[i]=='(') a[i]=a[i-]+; else
if (s[i]==')') a[i]=a[i-]-; else
a[i]=a[i-];
int p=,mx=;
for (int i=x;i<=y;i++)
{
if (a[i]==)
if (s[i]=='^' && level(s[i])<mx || s[i]!='^' && level(s[i])<=mx )
{
p=i;
mx=level(s[i]);
}
}
pii left=solve(x,p-,heap+,op);
int now=op+left.second+;
pii right=solve(p+,y,heap+,now+);
w[++tmp]=(node){op+left.first-,op+left.second+,now+right.first+-,heap,s[p]};
return pii(left.second+,left.second++right.second);
}
int cmp(const node &a,const node &b)
{
return a.len<b.len || a.len==b.len && a.mid<b.mid;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>s;
pii p=solve(,s.length()-,,);
sort(w+,w+tmp+,cmp);
for (int h=;h<=w[tmp].len;h++)
{
int i,j;
for (i=;w[i].len!=h;i++);
for (j=i;w[j+].len==h;j++);
if (h!=)
{
for (int t=;t<=w[i].mid-;t++) printf(" ");
printf("|");
for (int k=i+;k<=j;k++)
{
for (int t=w[k-].mid+;t<=w[k].mid-;t++) printf(" ");
printf("|");
}
printf("\n");
}
for (int t=;t<=w[i].l-;t++) printf(" ");
if (level(w[i].ch)!=) printf(".");
for (int t=w[i].l+;t<=w[i].mid-;t++) printf("-");
if (level(w[i].ch)!=) printf("[");
printf("%c",w[i].ch);
if (level(w[i].ch)!=) printf("]");
for (int t=w[i].mid+;t<=w[i].r-;t++) printf("-");
if (level(w[i].ch)!=) printf(".");
for (int k=i+;k<=j;k++)
{
for (int t=w[k-].r+;t<=w[k].l-;t++) printf(" ");
if (level(w[k].ch)!=) printf(".");
for (int t=w[k].l+;t<=w[k].mid-;t++) printf("-");
if (level(w[k].ch)!=) printf("[");
printf("%c",w[k].ch);
if (level(w[k].ch)!=) printf("]");
for (int t=w[k].mid+;t<=w[k].r-;t++) printf("-");
if (level(w[k].ch)!=) printf(".");
}
printf("\n");
}
}
最新文章
- JSP复习整理(四)Cookie
- c#设计模式-组合模式
- ES6新特性:Javascript中内置的延迟对象Promise
- Node Server管理
- 南昌PHP程序员的工资水平据说可达到8000了
- BFC——块级格式上下文
- iOS开发之文件(分段)下载
- Android开发技巧——自定义控件之使用style
- qml layout
- mysql5.7.17源码安装
- 关于信号打断正在读取终端的read与select来监视0文件描述符的问题
- 封装input 逐渐,且input插件必须带有默认值。
- Jenkins修改workspace和build目录
- iOS7.0中UILabel高度调整注意事项
- goim源码分析与二次开发-comet分析一
- CentOS 使用命令设置代理
- 列表框清屏/CListBox清空
- VG 859使用
- 用仿ActionScript的语法来编写html5——第六篇,TextField与输入框
- JPEGView——专业、免费、开源的图像浏览器