递归算法实例应用（二）

Polish Expression

Description

A Polish expression is an arithmetic expression that prepositions an operator. For example, the Polish representation of the ordinary expression 2 + 3 is + 2 3. The advantage of Polish expressions is that there is no need for precedence between operators, nor for parentheses to change the order of operations. For example, the Polish representation of (2 + 3) * 4 is * + 2 3 4. This problem evaluates the value of the Polish expression, where the operators include ‘+’,‘-’,‘*’,‘/’.

Input

The input is a line with Spaces separating both the operator and the operand, which is a floating-point number.

Output

The output is a line, the value of the expression.

Sample Input

* + 11.0 12.0 + 24.0 35.0

Sample Output

1357.000000

关于前缀表达式，又称波兰表达式，它是一种不需要括号的计算表达式的表示法。它将操作符号写在操作数之前，即二元运算符总是置于与之相关的两个运算对象之前，而每一个对象也可以是一个波兰表达式，因此波兰式是一个明显的以递归形式定义的问题。所以我们可以采用递归的方式进行解决。

同时，在数据结构栈相关章节，也有更为详细的阐述，主要是通过栈的方法将我们所熟知的中缀表达式转为后缀表达式（逆波兰表达式）或前缀表达式（波兰表达式），因为在计算机中通过前缀、后缀表达式相比于中缀表达式有着更广、更深的用途，只需入栈和出栈就可以搞定任何普通中缀表达式的运算。简言之为：如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。具体通过栈来模拟算法转换在此不加阐述，本文属递归篇，所以通过递归形式来解决问题。

算法思想：

当仅通过递归来实现时，相比于栈操作问题会变得更加简单。

所以，我们从波兰式的定义出发：

1. 一个数是一个波兰表达式，值为数本身。
2. “运算符” “波兰表达式1” “波兰表达式2” 是一个波兰表达式，值为波兰表达式1 运算符 波兰表达式2的值。

发现该定义本身是一个以递归形式来定义的，如2中，在定义波兰式时又用到了波兰式的概念，所以波兰式是一个以递归形式定义的问题。

而在1中，该条定义是明确的一条定义，并没有递归的定义形式出现。

波兰式的递归形式之所以成立，是因为1中这条非递归形式的定义在约束，作为递归的终止条件。也就是说，因为1中定义的存在使得2中的定义不存在无限循环定义的形式，使得波兰式的递归形式成立。

当对于波兰式的递归定义形式清楚以后问题就迎刃而解。

由于C/C++语言具有输入/输出缓冲区的特性，所以可以在程序等待输入时一次性将待输入字符串输入完整。

代码逻辑：

1. 依次读入每一个字符串

2. 判断字符串类型：

   • 若该字符串为‘+’，则后两个字符串应该为波兰式1和波兰式2，并对两波兰式做加法运算，其值作为返回值。
   • 若该字符串为‘-’，则后两个字符串应该为波兰式1和波兰式2，并对两波兰式做减法运算，其值作为返回值。
   • 若该字符串为‘*’，则后两个字符串应该为波兰式1和波兰式2，并对两波兰式做乘法运算，其值作为返回值。
   • 若该字符串为‘/’，则后两个字符串应该为波兰式1和波兰式2，并对两波兰式做除法运算，其值作为返回值。
   • 若该字符串为数字，则根据定义1可知，改波兰式的值为该值本身，所以返回该字符串对应的双浮点数类型即可，可通过stdlib.h头文件中atof()函数进行转换。
3. 输出波兰式的值

代码整合：

double PolishExp() {
    char str[20];
    scanf("%s", str);
    switch (str[0]) {
        case '+':
            return PolishExp() + PolishExp(); // +ab -> a+b
        case '-':
            return PolishExp() - PolishExp(); // -ab -> a-b
        case '*':
            return PolishExp() * PolishExp(); // *ab -> a*b
        case '/':
            return PolishExp() / PolishExp(); // /ab -> a/b
        default:
            return atof(str); //将字符串转为双浮点数类型
    }
}

By Ss1Two 2023/01/14