查人人中国名人网太空舱 中医 检测:波兰逆序问题
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/29 21:32:09
1) 先计算括号内，后计算括号外；
2) 在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级；
3) 同一优先级运算，从左向右依次进行。
在这种表达式的计算过程中，既要考虑括号的作用，又要考虑运算符的优先级，还要考虑运算符出现的先后次序。
波兰科学家卢卡谢维奇(Lukasiewicz)提出了算术表达式的另一种表示，即后缀表示，又称逆波兰式，其定义是把运算符放在两个运算对象的后面。在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成。
例如
3/5+6的逆波兰表达式为3 5 / 6 +
2*(3+4)的逆波兰表达式为2 3 4 + *
输入
一个只包含加、减、乘、除和数字的逆波兰表达式
输出
该表达式的值
测试输入 2 3 + 5 *
期待的输出 25
一楼的我试过了，没有用啊。
最好有注释，为了学习。
/*通过gcc编译，不过只支持整数运算……
晕，原来是没有声明char express[],而且忘了初始化top=-1;
忘记#define<string.h>可能这样Tc就不行了
现在好了，不过你只能将表达式输入到一行里，
输入空行退出程序
还有我这里面一共有两个程序，用
/*******************/分开的，看清楚了再用哦。
主要思想是用到了栈这个数据结构（后进先出）
如果遇到数字，就压栈
如果遇到符号，则将栈顶前两个数字取出进行运算，再将结果压栈。
我的这个程序没有表达式输入是否正确的检查，也就是如果输入错误的表达式，会引发程序错误
*/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
int stack[1024],top=-1;
int work(char * exp)
{
int prvIsDigit=0;
int tmp,i,length=strlen(exp);
top=-1;
for(i=0;i<length;++i)
{
/*这一步是判断并提取表达式中的数字*/
if(isdigit(exp[i]))
{
if(prvIsDigit) stack[top]=stack[top]*10+exp[i]-'0';
else stack[++top]=exp[i]-'0';
prvIsDigit=1;
}
else prvIsDigit=0;
/*这步就是判断符号，进行运算*/
if(exp[i]=='+') {
tmp=stack[top--];
stack[top]+=tmp;
}
if(exp[i]=='-') {
tmp=stack[top--];
stack[top]-=tmp;
}
if(exp[i]=='*') {
tmp=stack[top--];
stack[top]*=tmp;
}
if(exp[i]=='/') {
tmp=stack[top--];
stack[top]/=tmp;
}
}
/*如果表达式正确，栈内一定只剩一个元素，这个元素就是结果*/
return stack[0];
}
int main()
{
char express[256];
while(1)
{
gets(express);/*将以行的内容存放到express中*/
if(strlen(express)==0) break;
/*如果是空行则退出*/
printf("%d\n",work(express));/*输出表达式的值*/
}
}
/******************************************************************************************************************************************************/
/*又写了个浮点数的没有用库函数atof,嘿嘿*/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
double stack[1024];
int top=-1;
double work(char * exp)
{
double tmp,afterPoint=0;
int i,length=strlen(exp);
int prvIsDigit=0;
top=-1;
for(i=0;i<length;++i)
{
if(isdigit(exp[i]))
{
if(prvIsDigit&&afterPoint==1) stack[top]=stack[top]*10+exp[i]-'0';
else if(prvIsDigit)
{
stack[top]+=(exp[i]-'0')*afterPoint;
afterPoint*=.1;
}
else
{
stack[++top]=exp[i]-'0';
afterPoint=1;
}
prvIsDigit=1;
}
else if(exp[i]=='.') afterPoint=.1;
else prvIsDigit=0;
if(exp[i]=='+') {
tmp=stack[top--];
stack[top]+=tmp;
}
if(exp[i]=='-') {
tmp=stack[top--];
stack[top]-=tmp;
}
if(exp[i]=='*') {
tmp=stack[top--];
stack[top]*=tmp;
}
if(exp[i]=='/') {
tmp=stack[top--];
stack[top]/=tmp;
}
}
return stack[0];
}
int main()
{
char express[256];
while(1)
{
gets(express);
if(strlen(express)==0) break;
printf("%lf\n",work(express));
}
return 0;
}