NYOJ 35 表达式求值(逆波兰式求值)
2024-10-19 02:18:55
http://acm.nyist.net/JudgeOnline/problemset.php?typeid=4
NYOJ 35 表达式求值(逆波兰式求值)
逆波兰式式也称后缀表达式。
一般的表达式求值式子都为中缀表达式,而后缀表达式求值相对更容易,所以可以将中缀表达式转换为后缀表达式。
ps:不了解中缀表达式,后缀表达式的建议先去了解一下。
对于初学者容易弄混这三种,其实前,中,后即节点位置。
前缀表达式树,遍历顺序(节点,左,右)。
中缀表达式树,遍历顺序(左,节点,右)。
后缀表达式树,遍历顺序(左,右,节点)。
步骤:
第一步:将中缀表达式转换为后缀表达式。
1,将+,-,*,/,(等要用到的运算进行优先级处理。
2,需要用到一个符号栈处理:
a,数字字符,小数点直接存入另一个字符串S。
b,’(‘直接入栈,当表达式str字符中‘)’出现,将所有栈顶运算符转移至S直至遇到‘(’,‘(’出栈。
c,当表达式str字符中的运算符优先级大于等于(注意一定要大于等于)栈顶运算符优先级时,将字符依次存入S,直至小于为止。当前运算符入栈。
d,最后当str访问完,将栈中剩余运算符存到S。
第二步:将转换后的后缀表达式进行求值。
1,需要一个浮点型栈(具体根据题目要求)存放数值。
2,遍历S遇见操作数,小数点时处理后入栈,直至遇见运算符,出栈两个操作数,处理后将结果再入栈。
3,栈顶元素即为表达式解。
主要注意:
1.小数点的处理。
2,细心。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int maxn=+; string s1,s2;
stack<char> s;
stack<double> c; void init()
{
while(!s.empty())
s.pop();
while(!c.empty())
c.pop();
} int pro(char ch)
{
switch(ch)
{
case '+':
case '-':return ;
case '*':
case '/':return ;
default :return ;
}
} void deal()
{
init();
int i=,len=s1.length();
s.push('#');
while(i<len-)
{
if(s1[i]=='(')
s.push(s1[i++]);
else if(s1[i]==')')
{
while(s.top()!='(')
{
s2+=s.top();
s2+=' ';
s.pop();
}
s.pop();
i++;
}
else if(s1[i]=='+'||s1[i]=='-'||s1[i]=='*'||s1[i]=='/')
{
while(pro(s.top())>=pro(s1[i]))
{
s2+=s.top();
s2+=' ';
s.pop();
}
s.push(s1[i]);
i++;
}
else
{
while(s1[i]<=''&&s1[i]>=''||s1[i]=='.')
s2+=s1[i++];
s2+=' ';
}
}
while(s.top()!='#')
{
s2+=s.top();
s.pop();
s2+=' ';
}
} double countt()
{ int len=s2.length(),i=;
double y,x;
while(i<len)
{
if(s2[i]==' ')
i++;
else
{
switch(s2[i])
{
case '+':x=c.top();c.pop();x+=c.top();c.pop();i++;break;
case '-':x=c.top();c.pop();x=c.top()-x;c.pop();i++;break;
case '*':x=c.top();c.pop();x*=c.top();c.pop();i++;break;
case '/':x=c.top();c.pop();x=c.top()/x;c.pop();i++;break;
default :
{
x=0.0;
while(s2[i]<=''&&s2[i]>='')
x=x*+(s2[i++]-'');
if(s2[i]=='.')
{
i++;
double k=10.0;y=0.0;
while(s2[i]<=''&&s2[i]>='')
{
y+=(s2[i++]-'')/k;
k*=;
}
x+=y;
}
}
}
c.push(x);
}
}
return c.top();
} int main()
{
int t;
cin>>t;
while(t--)
{
cin>>s1;
s2="";
deal();
printf("%.2lf\n",countt());
}
return ;
}
参考大神博客后,AC了的总结。
不喜勿喷,欢迎赐教,欢迎一起交流
最新文章
- 错误:ORA-28009: connection as SYS should be as SYSDBA or SYSOPER 的解决办法--转载但验证过后可以用
- jade转化为html
- genymotion是一款完全超越BlueStacks
- angularJS中如何写服务
- window.open窗口居中和窗口最大化
- mudOS配置
- 常用Python第三方库 简介
- 【NOIP2015提高组】Day1 t1神奇的幻方
- 多项式求导系列——OO Unit1分析和总结
- WEB前端常见面试题汇总:(一)
- (五)Cluster Health
- HTTP请求中的Keep-Alive模式,是怎么区分多个请求的?
- np.meshgrid()用法+ np.stack()用法
- 【Alpha】Scrum Meeting 2
- android 读取本地json文件 解决显示乱码显示
- python 搜索引擎Whoosh中文文档和代码 以及jieba的使用
- 每天一个linux命令:wc命令
- Discrete Square Roots UVALive - 4270(拓展欧几里得)
- 算法学习 - 平衡二叉查找树实现(AVL树)
- js中的冒泡排序
热门文章
- mybatis使用*号查询数据丢失问题
- vscode调试html文件
- HTML5中的拖拽与拖放(drag&;&;drop)
- mysql的docker化安装
- 【每天一条Linux指令-Day1】kill掉多个mysql的进程
- Spark运行模式_基于YARN的Resource Manager的Custer模式(集群)
- MySQL集群-PXC搭建以及使用innobackupex工具进行全局备份和增量备份
- PTA基础编程题目集7-3逆序三位数
- 第三节 循环链表的Go语言实现
- HyperLedger Fabric 1.4 Solo模式简介(10.1)