算法实践：波兰表达式

波兰表达式

描述

逆波兰表达式，英文为 Reverse Polish notation，跟波兰表达式（Polish notation）相对应。之所以叫波兰表达式和逆波兰表达式，是为了纪念波兰的数理科学家 Jan Łukasiewicz。其在著作中提到：

我在1924年突然有了一个无需括号的表达方法，我在文章第一次使用了这种表示法。

• 平时我们习惯将表达式写成 (1 + 2) * (3 + 4)，加减乘除等运算符写在中间，因此称呼为中缀表达式。
• 而波兰表达式的写法为 (* (+ 1 2) (+ 3 4))，将运算符写在前面，因而也称为前缀表达式。
• 逆波兰表达式的写法为 ((1 2 +) (3 4 +) *)，将运算符写在后面，因而也称为后缀表达式。

波兰表达式和逆波兰表达式有个好处，就算将圆括号去掉也没有歧义。上述的波兰表达式去掉圆括号，变为* + 1 2 + 3 4。逆波兰表达式去掉圆括号，变成1 2 + 3 4 + *也是无歧义并可以计算的。事实上我们通常说的波兰表达式和逆波兰表达式就是去掉圆括号的。而中缀表达式，假如去掉圆括号，将 (1 + 2)(3 + 4) 写成 1 + 23 + 4，就改变原来意思了。

（作者：黄兢成链接：https://www.zhihu.com/question/41103160/answer/452481026来源：知乎）

(2 + 3) * 4`的波兰表示法为`* + 2 3 4

请写程序求解波兰表达式的值。

本题输入的运算符只包括如下4个运算符：+ - * /

输入

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

输出

输出为一行，表达式的值。

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

样例

* + 11.0 12.0 + 24.0 35.0

1357.000000

难度

中，栈 and 递归

代码

code by guowei

code by me

#include <bits/stdc++.h>  //万能头文件
using namespace std;
stack<double>st;
double compute(double a,double b,string  c){
    if(c=="+"){
        return a+b;
    }
    else if(c=="-"){
        return a-b;
    }
    else if(c=="*"){
        return a*b;
    }
    else{
        return a*1.0/b;
    }
}
int main()
{
    string s[31];
    int i=0;
    double a,b;
    int flag=0;
    while(cin>>s[i]){
        i++;
    }
    for(int j=i-1; j>=0; --j){
        if(s[j]=="+"||s[j]=="-"||s[j]=="*"||s[j]=="/")//遇到符号从栈中弹出两个个值
        {
            a = st.top();
            st.pop();
            b = st.top();
            st.pop();
            st.push(compute(a,b,s[j]));
        }
        else  //如果是操作数就转换成数压栈
        {
            st.push(atof(s[j].c_str()));
        }
    }
    printf("%.6f",st.top());
    return 0;
}