MENU

波兰表达式

March 24, 2018 • Read: 297 • 算法

题目

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

样例输入

* + 11.0 12.0 + 24.0 35.0

样例输出

1357.000000

提示

(11.0+12.0)*(24.0+35.0)

题解

波兰表达式的定义:

  1. 一个数是波兰表达式,值为该数.
  2. 波兰表达式的形式为:“运算符 波兰表达式波兰表达式”,值为两个波兰表达式的值运算的结果.

其实我们仔细看第二点,就会发现,这是一个很明显的递归,“波兰表达式 = 运算符 波兰表达式 波兰表达式”,而第一点类似于递归的出口,当一个数是波兰表达式时,值为该数.

代码

#include <bits/stdc++.h>
using namespace std;
double exp()
{
        char s[20];
        cin>>s;
        switch(s[0])
        {
               case'+':return exp()+exp();
               case'-':return exp()-exp();
               case'*':return exp()*exp();
               case'/':return exp()/exp();
               default:return atof(s);//如果为数,则直接返回这个数 
               break;
        } 
} 
int main()
{
        printf("%lf",exp());
        return 0;
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment