1696:逆波兰表达式

http://noi.openjudge.cn/ch0303/1696/

总时间限制: 

1000ms

内存限制: 

65536kB

描述

逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。

输入

输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。

输出

输出为一行，表达式的值。
可直接用printf("%f\n", v)输出表达式的值v。

样例输入

* + 11.0 12.0 + 24.0 35.0

样例输出

1357.000000

1、本题的题目错了，这应该是波兰表达式，也叫做前缀表达式。逆波兰表达式是后缀表达式，即操作符在数字的后面

2、前缀表达式：http://baike.so.com/doc/6896516-7114163.html

前缀表达式的计算方法：从右往左扫描表达式，只要碰到数字就入栈；碰到运算符，弹出栈顶的两个数字运算，注意如果是减号或除号，要用 栈顶数字 除或减 次栈顶数字。

3、本题为了方便操作，可以从左往右分别记录了第几个元素是哪个数字或是哪个运算符。分别存储在tmp[]、num[]中，但记录下标时，两个数组共用1个sum。
所以判断第i个是数字还是运算符时，首先给num[]赋一个极值，然后判断如果num[]是极值，那么第i个是运算符，如果不是极值，那就是数字。注意极值不能为0，因为给出的数字可能为0

4、可以使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在cmath中。待转换的字符串要用char数组存储，一定要注意下标从0开始，小数点也要存到char数组里。例：char a[20]=“123.456”；double l=atof（a）；输出结果为123.456

#include<cmath>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#define no -999999999

using namespace std;

char k[];

char s[],tmp[];

double num[];

int l=-,sum,top;

double stack[],ans;

int main()

{

     gets(s);

     for(int i=;i<=;i++) num[i]=no;//num数组赋极值

     for(int i=;i<=strlen(s);i++)

     {

         if(s[i]==||s[i]==||s[i]==||s[i]==) tmp[++sum]=s[i];//运算符

        else if((s[i]>=''&&s[i]<='')||s[i]==) k[++l]=s[i];//数字或者小数点

        else if(s[i-]>=''&&s[i-]<='') //只有数字之后的空格才需要把字符串转换成数字

        {

            num[++sum]=atof(k);

            memset(k,'\0',sizeof(k));

            l=-;//l从-1开始，因为上面k[++l]=s[i]，数组k从0开始赋值

        }

     }

     for(int i=sum;i>;i--)//从右往左扫描

     {

         if(num[i]!=no) stack[top++]=num[i];//不是极值，是数字，入栈

         else //运算符，弹出栈顶两个数字运算

         {

             double a=stack[--top],b=stack[--top];

            switch(tmp[i])

             {

                 case '+':ans=a+b;break;

                 case '-':ans=a-b;break;

                 case '*':ans=a*b;break;

                 case '/':ans=a/b;break;

            }

            stack[top++]=ans;//运算完结果入栈

        }

     }

     printf("%f\n",stack[]);

}