M02694: 波兰表达式

recursion, strings, http://cs101.openjudge.cn/pctbook/M02694/

波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式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

提示

可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。 此题可使用函数递归调用的方法求解。

来源：计算概论05

2021fall-cs101，王顾言。

这道题理解题意花了不少时间，对题目下面给出的使用递归函数求解更是迷惑。 个人觉得和 OJ.03704括号匹配 问题非常相似，手动建了个栈，一通操作后ac。 做完后去看题解，画了个流程图才理解 递归解法 绝妙之处。

2021fall-cs101，欧阳韵妍。

解题思路：关键：碰到两个数字就按照离两个数字左边最近的运算符运算，注意由于输入的是 str，需要手动定义输入的运算符对应的运算操作。注意 operate 是一层层套下去的，比如：* + 11.0 12.0 + 24.0 35.0 就是这样的运算步骤：

（）*（）→

（（）+（））*（）→

（（11.0）+（12.0 ））* （）→

（（11.0 ）+ （12.0 ））* （（）+ （））→

（（11.0 ）+ （12.0 ））*（（24.0）+（35.0））

一个运算符相当于进行一次递归。学会了输出精确到两位小数点的方法，用”{:.2f}”.format()。

'''
前缀表达式是运算符在前，操作数其后，
就是假如碰到一个运算符，其后就需要有连续的两个操作数才能运算消去，
否则就一直等待输入或者等待后面的运算结束得到操作数,
这恰好能用递归实现。
'''
# pylint: skip-file
def Exp():
    global pos
    pos += 1
    chr = calculatelist[pos]
    if chr == '+':
        return Exp() + Exp()
    elif chr == '-':
        return Exp() - Exp()
    elif chr == '*':
        return Exp() * Exp()
    elif chr == '/':
        return Exp() / Exp()
    else:
        return float(chr)



calculatelist = []
pos = -1
calculatelist = list(input().split())
result = Exp()
print(f"{result:.6f}")

2021fall-cs101，李文梁。

由于python 可以直接计算字符串表达式，只需要把波兰表达式转换成正常计算式即可。具体操作为递归，嵌套到从最内层开始把符号换到数字之间并计算，一层层返回即可。

s = input().split()
def cal():
    cur = s.pop(0)
    if cur in "+-*/":
        return str(eval(cal() + cur + cal()))
    else:
        return cur

print(f"{float(cal()):.6f}")

2021fall-cs101，黄湘榆。

这题像是一道语法题。我利用了之前做24 点时学到的operator 标准库来定义一个运算符的字典，方便随时根据需求切换运算符。

import operator 
op = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}

import operator 
s = input().split() 
op = {"+": operator.add, "-": operator.sub, "*": operator.mul, 
"/": operator.truediv} 
while len(s) != 1: 
    for i in range(len(s)): 
        if s[i][0].isdecimal() and s[i+1][0].isdecimal(): 
            o = s.pop(i-1) 
            a = s.pop(i-1) 
            b = s.pop(i-1) 
            c = op[o](float(a), float(b)) 
            s.insert(i-1, str(c)) 
            break 
 
print(f"{float(s[0]):.6f}")

2021fall-cs101，陈锦洋。

不得不说eval 函数在这里帮了大忙。递归在这里是很好的想法。

l=input().split()
def poland():
    op=l.pop(0)
    a=poland() if l[0] in '+-*/' else l.pop(0)
    b=poland() if l[0] in '+-*/' else l.pop(0)
    return eval(str(a)+op+str(b))
print(f'{poland():.6f}')

2021fall-cs101，陈思同。

break用的挺巧妙，悬崖勒马的感觉。明明边循环边删除，就要出错了感觉。

b = ['+', '-', '*', '/']
a = input().split()
for i in range(len(a)):
    if a[i] not in b: a[i] = float(a[i])
while 1:
    if len(a) == 1:
        break
    for i in range(len(a)):
        if a[i] in b and a[i+1] not in b and a[i+2] not in b:
            if a[i] == '+': d = a[i+1] + a[i+2]
            elif a[i] == '-': d = a[i+1] - a[i+2]
            elif a[i] == '*': d = a[i+1] * a[i+2]
            elif a[i] == '/': d = a[i+1] / a[i+2]
            
            a[i] = d
            del a[i+1] 
            del a[i+1]
            break
print(f'{a[0]:.6f}')

2021fall-cs101，渠成锐。

思路：最一开始接触到函数递归调用就是这道题，当时惊赞题解里的做法真的是妙哉。现在学了栈这种数据结构，我发现可以写一个不用函数递归调用的版本。基本想法如下：从后往前读取表达式，碰见数字则压入栈，碰见运算符号则从栈顶弹出两个数据进行计算，将计算结果再压入栈即可。

expression = input().split()
stack = []
while expression:
    a = expression.pop(-1)
    if a in ['+', '-', '*', '/']:
        c = stack.pop(-1)
        d = stack.pop(-1)
        if a == '+':
            stack.append(c + d)
        elif a == '-':
            stack.append(c - d)
        elif a == '*':
            stack.append(c * d)
        else:
            stack.append(c / d)
    else:
        stack.append(float(a))
        
print(f"{stack[0]:.6f}")

2021fall-cs101，周稚坤。

逆波兰是运算符号尽量往后。https://en.wikipedia.org/wiki/Reverse_Polish_notation 转化为逆波兰表达式更有利于理解“栈”的概念，通过这个题我对栈的理解有了一定加深。首先要明确逆波兰表达式的基本运算为： （逆波兰表达式1）算符（逆波兰表达式2）=（逆1）（逆2）算符 重复操作后会发现这是一个树的结构，那么其中一种方法就是以一个树根开始一步步向上走，并将遇上的数堆到栈里。每当遇上符号，则进行一次上述运算并拿走栈上最上面的两个值，以此往复到最后自然只剩下运算结果，输出即可。

这里第一次知道eval 函数用来执行一个字符串表达式，并返回表达式的值。 尝试学习了李文梁同学的递归代码，自己认为这和“递归的本质就是不要关心递归的那个函数究竟发生了什么”有很大关联。只要记住最基本的（逆波兰表达式1）算符（逆波兰表达式2）=（逆1）（逆2）算符 就好。

# http://cs101.openjudge.cn/practice/02694/

D=input().split()
D.reverse()
def STACK(D):
    stack=[]
    for i in D:
        if i in '+-*/':
            a=stack.pop()
            b=stack.pop()
            stack.append(str(eval(a+i+b)))
        else:
            stack.append(i)
    return stack[0]
print('%6f'% float(STACK(D)))

2022fall-cs101，余力圣，化学与分子工程学院。正则表达式解法，可以在这里验证，https://regex101.com。

import re
sig = re.compile(r'[\+\-\*/][ ][^ \+\-\*/]+[ ][^ \+\-\*/]+')

def cal(s):
    par = re.search(sig, s)
    if par == None: 
        return s
    
    p = str(par.group()).split()
    #print(p)
    s = re.sub(sig, str(eval(p[1]+p[0]+p[2])), s, count=1)
    #print(s)
    #print()
    return cal(s)

x = input()
print('%f'%(float(cal(x))))