看了逆波兰表达式之后,发现真是强悍的数据结构,栈的应用怎么感觉一辈子也学不完了呢

后缀表达式即逆波兰表达式,就是将所有的运算符按照一定的等级全部都安排到数字的后面去,实现正确的运算法则。

OK,代码要自己好好看,理解了自然就很简单。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<time.h>
using namespace std;
int const N = ;
int hash[N];
char exp1[N],exp2[N],a1[N],a2[N],stack1[N];
int stack2[N];
int cal(char exp[],char a[],int len,char stack[])
{
int topa=,tops=;
for(int i=;i<len;i++)
{
if((exp[i]<=''&&exp[i]>='')||(exp[i]<='Z'&&exp[i]>='A')||(exp[i]<='z'&&exp[i]>='a'))
a[topa++]=exp[i];
else
{
if(exp[i]=='+'||exp[i]=='-')
{
while(tops>&&stack[tops-]!='(')
a[topa++]=stack[--tops];
stack[tops++]=exp[i];
}
else
if(exp[i]=='*')
{
while(tops>&&stack[tops-]!='('&&stack[tops-]!='+'&&stack[tops-]!='-')
a[topa++]=stack[--tops];
stack[tops++]=exp[i];
}
else
if(exp[i]==')')
{
while(stack[tops-]!='(')
a[topa++]=stack[--tops];
tops--;
}
else
if(exp[i]=='(')
stack[tops++]=exp[i];
}
}
while(tops>)
a[topa++]=stack[--tops];
return topa;
}
int Count(char a[],int len,int stack[])
{
int tops=;
for(int i=;i<len;i++)
{
if(a[i]>=''&&a[i]<='')
stack[tops++]=a[i]-'';
else
if((a[i]>='A'&&a[i]<='Z')||(a[i]>='a'&&a[i]<='z'))
stack[tops++]=hash[a[i]];
else
{
if(a[i]=='*')
stack[tops-]=stack[tops-]*stack[tops-];
else
if(a[i]=='-')
stack[tops-]=stack[tops-]-stack[tops-];
else
if(a[i]=='+')
stack[tops-]=stack[tops-]+stack[tops-];
tops--;
}
}
return stack[];
}
int main()
{
srand(time());
int T;
cin>>T;
gets(exp1);
while(T--)
{
gets(exp1);
gets(exp2);
int len1=strlen(exp1);
int len2=strlen(exp2);
len1=cal(exp1,a1,len1,stack1);
len2=cal(exp2,a2,len2,stack1);
int f=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
hash[j]=rand()%;
int ans1=Count(a1,len1,stack2);
int ans2=Count(a2,len2,stack2);
if(ans1!=ans2)
{
f=;break;
}
}
if(f)printf("YES\n");
else printf("NO\n");
}
return ;
}

最新文章

  1. Servlet页面登录的数据库验证程序(二)
  2. 关于&lt;meta http-equiv=&quot;X-UA-Compatible&quot; content=&quot;IE=edge&quot; /&gt;问题
  3. jsti 和EL用法注意点
  4. 从本地向 Github 上传项目步骤攻略(快速上手版)
  5. cocos2d-js 3.0rc0加载游戏引擎时长时间黑屏
  6. C++ string 转 char*
  7. 怎么样能让自己的虚拟机上网win7 for linux
  8. 安卓 unit 测试与 instrument 测试的代码共享
  9. phpMyAdmin import.php 跨站脚本漏洞
  10. 详解linux vi命令用法
  11. DOM对象和JQuery有什么不同的地方?
  12. MySql绿色版安装过程记录
  13. nodejs querystring踩坑笔记----只能用于表单提交
  14. 【SqlServer系列】聚合函数
  15. xml的SAX解析和dom解析的区别
  16. Android光线传感器-android学习之旅(65)
  17. InterLocked学习笔记
  18. yii2部署nginx
  19. 6th week blog(1)
  20. scrapy 发送post请求

热门文章

  1. C++输入结束
  2. WIX Custom Action (immediate, deffered, rollback)
  3. Config spec rules for elements in subbranches
  4. Headfirst设计模式的C++实现——适配器(Adapter)
  5. Django部署问题
  6. textarea限定字数提示效果
  7. 修改VC++2010界面左上角图标
  8. java JDBC操作MySQL数据库
  9. MVC5 ModelBinder
  10. nodejs基础安装