文档章节

逆波兰表达式的转化与求值(python实现)

vision_zwx
 vision_zwx
发布于 2017/07/19 10:54
字数 1231
阅读 805
收藏 0

目前,大多数编程语言都能直接计算类似于9 + ( 3 - 1 ) * 3 + 10 / 2这样的表达式,本文从数据结构的层次上讲解具体的实现算法,首先搞懂以下两个定义:

中缀表达式: 在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称 为中缀表达式,简单来说,我们平常见到的运算表达式就叫中缀表达式;

后缀表达式: 又叫逆波兰表达式 ,不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 的后缀表达式为2 1 + 3 *

中缀表达式就不多介绍了,大家都比我还明白,那么看看逆波兰表达式是如何转化而来的,先给几个小例子热热身体 (a+b ---> a,b,+                   a+(b-c)*d ---> a,b,c,-,d,*,+                       a+(b-c) ---> a,b,c,-,+)

一、 将 中缀表达式s=“9 + ( 3 - 1 ) * 3 + 10 / 2”变为后缀表达式s_after = "9 3 1 - 3 * + 10 2 / +",具体的规则如下 :

首先维护两个空栈,(stack_exp)存逆波兰表达式,(stack_ops)暂存操作符,运算结束后stack_ops必为空循环遍历字符串(将表达式分为四种元素 1、数值; 2、操作符; 3、 左括号; 4、右括号),具体情况如下:

1、遇到数值, 将该值入栈stack_exp

2、遇到左括号, 将左括号入栈stack_ops

3、遇到右括号,将stack_ops中的操作符从栈顶依次出栈并入栈stack_exp, 直到第一次遇到左括号终止操作(注意: 该左括号出栈stack_ops但不入栈stack_exp)至此消除表达式中的一对括号

4、遇到四则运算操作符号(+ - * /)

         4-1、 如果stack_ops为空, 操作符入栈stack_ops

         4-2、 如果stack_ops不空,将stack_ops栈顶操作符与遍历到的操作符(op)比较:

                4-2-1: 如果stack_ops栈顶操作符为左括或者op优先级高于栈顶操作符优先级, op入栈                                           stack_ops,当前遍历结束

                4-2-2: 如果op优先级小于或者等于stack_ops栈顶操作符, stack_ops栈顶操作符出栈并入栈                                     stack_exp,重复4-1、 4-2直到op入栈stack_ops

5、字符串遍历结束后如果stack_ops栈不为空,则依次将操作符出栈并入栈stack_exp

代码实现(python版本)

# 运算规则,先乘除,后加减.
ops_rule = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2
}


def middle_to_after(s):
    """
    中缀表达式转化后缀表达式.
    :param s: 中缀表达式的字符串表示,本程序中采用操作符跟数值之间用空格分开,例如:
    "9 + ( 3 - 1 ) * 3 + 10 / 2"
    :return: 后缀表达式,数组的形式,每个数值或者操作符占一个数组下标.
    """
    expression = []
    ops = []
    ss = s.split(' ')
    for item in ss:
        if item in ['+', '-', '*', '/']:   # 操作符
            while len(ops) >= 0:
                if len(ops) == 0:
                    ops.append(item)
                    break
                op = ops.pop()
                if op == '(' or ops_rule[item] > ops_rule[op]:
                    ops.append(op)
                    ops.append(item)
                    break
                else:
                    expression.append(op)
        elif item == '(':  # 左括号,直接入操作符栈
            ops.append(item)
        elif item == ')':  # 右括号,循环出栈道
            while len(ops) > 0:
                op = ops.pop()
                if op == '(':
                    break
                else:
                    expression.append(op)
        else:
            expression.append(item)   # 数值,直接入表达式栈

    while len(ops) > 0:
        expression.append(ops.pop())

    return expression

二、将后缀表达式s_after = "9 3 1 - 3 * + 10 2 / +" 求值,具体的规则如下 :

初始化一个数值栈stack_value,用于存放中间数值以及计算结果

遍历s_after:

1、如果遇到数字,入栈stack_value;

2、如果遇到运算符, 从stack_value中依次出栈两个数(先出栈的在右, 后出栈的在左 )连同遍历到的运算符组成二目运算,求值后将结果压栈stack_value;

3、 继续遍历下一个元素,直到结束;

遍历完后stack_value中的结果便是表达式的值

代码实现如下(python):

def expression_to_value(expression):
    """
    :param expression: 后缀表达式的字符串表示,操作符跟数值间用空格分割,例如:
    "9 3 1 - 3 * + 10 2 / +"
    :return: 运算结果,一个值
    """
    stack_value = []
    for item in expression:
        if item in ['+', '-', '*', '/']:
            n2 = stack_value.pop()          # 注意,先出栈的在操作符右边.
            n1 = stack_value.pop()
            result = cal(n1, n2, item)
            stack_value.append(result)
        else:
            stack_value.append(int(item))   # 数值直接压栈.
    return stack_value[0]

def cal(n1, n2, op):
    if op == '+':
        return n1 + n2
    if op == '-':
        return n1 - n2
    if op == '*':
        return n1 * n2
    if op == '/':
        return n1 / n2

到此为止,这个后缀表达式的转化以及求解介绍完了,不知道大家整明白了吗,可以结合代码仔细研究,另外,如果有哪位朋友发现此文有误,欢迎留言告知,更多好文章,敬请期待...

© 著作权归作者所有

vision_zwx
粉丝 0
博文 1
码字总数 1231
作品 0
朝阳
私信 提问
计算逆波兰式

在程序设计中,可能碰到需要对字符串数学表达式求值的问题,常用的方法是解析表达式,生成二叉树,然后进行计算。编译器就是使用这种方法来解析程序中的表达式的。这种方法实现起来有点难度,...

一贱书生
2016/12/26
275
0
【讲古堂】表达式求值

【讲古堂】表达式求值 (dubenju@126.com 2015/12/27) 什么是表达式 表达式是由数字,操作符,变量,常量等有意义地组合而成并能求得结果的式子。 例如: 32 + ( ( 9 * Celsius ) / 5 ) 4 +...

壶漏子
2015/12/27
103
0
c代码填空,前缀表达式,递归,求解

标题:逆波兰表达式 正常的表达式称为中缀表达式,运算符在中间,主要是给人阅读的,机器求解并不方便。 例如:3 + 5 * (2 + 6) - 1 而且,常常需要用括号来改变运算次序。 相反,如果使用逆...

W-zq
2014/12/14
861
4
堆栈的应用——用JavaScript描述数据结构

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。 一、实现一个栈类Stack 基于堆栈的特性,可以...

我是leon
2018/08/10
0
0
逆波兰表达式求值 javascript版

代码地址: http://runjs.cn/code/r06uftvp 首先得弄明白什么是 逆波兰表达式 参见 : http://www.cnblogs.com/chenying99/p/3675876.html 大致总结一下 我们平常的计算方法, 运算符放在两个数...

云墨雪
2015/12/01
264
1

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周四乱弹 —— 当你简历注水但还是找到了工作

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @花间小酌 :#今日歌曲推荐# 分享成龙的单曲《男儿当自强》。 《男儿当自强》- 成龙 手机党少年们想听歌,请使劲儿戳(这里) @hxg2016 :刚在...

小小编辑
今天
2.9K
22
靠写代码赚钱的一些门路

作者 @mezod 译者 @josephchang10 如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。 今天给大家分享一个精彩的 GitHub 库,这个库整理...

高级农民工
昨天
5
0
用好项目管理工具,人人都可以成为项目经理

现在市面上的项目管理工具越来越多了,但是大多数都是一些协同工具或轻量项目管理工具。如果是多团队、跨部门使用或者企业级的项目管理,从管理思想到工具运用,需要适应企业的业务流程体系,...

cs平台
昨天
12
0
只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
69
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部