python 逆波兰式

逆波兰式,也叫后缀表达式

技巧:为简化代码,引入一个不存在的运算符#,优先级最低。置于堆栈底部

 

class Stack(object):
    '''堆栈'''
    def __init__(self):
        self._stack = []

    def pop(self):
        return self._stack.pop()

    def push(self, x):
        self._stack.append(x)
    

 

 一、表达式无括号

def solve(bds):
    '''不带括号,引入#运算符'''
    pro = dict(zip('^*/+-#', [3,2,2,1,1,0]))
    out = []
    s = Stack()
    s.push('#')
    for x in bds:
        if x in '^*/+-':
            t = s.pop()
            while pro[x] <= pro[t]:
                out.append(t)
                t = s.pop()

            s.push(t)
            s.push(x)
        else:
            out.append(x)

    while not s.is_null():
        out.append(s.pop())

    return out[:-1]
bds1 = 'a+b/c^d-e'          # abcd^/+e-
print(bds1, ''.join(solve(bds1)))

 

二、表达式有括号

def solve(bds):
    '''带括号,引入#运算符'''
    pro = dict(zip('^*/+-#', [3,2,2,1,1,0]))
    out = []
    s = Stack()
    s.push('#')
    for x in bds:
        if x == '(':            # ①左括号 -- 直接入栈
            s.push(x)
        elif x == ')':          # ②右括号 -- 输出栈顶,直至左括号(舍弃)
            t = s.pop()
            while t != '(':
                out.append(t)
                t = s.pop()
        elif x in '^*/+-':      # ③运算符 -- 从栈顶开始,优先级不小于x的都依次弹出;然后x入栈
            while True:
                t = s.pop()
                if t == '(':    # 左括号入栈前优先级最高,而入栈后优先级最低!
                    s.push(t)
                    break
                if pro[x] <= pro[t]:
                    out.append(t)
                else:
                    s.push(t)
                    break
            s.push(x)
        else:                   # ④运算数 -- 直接输出
            out.append(x)

    while not s.is_null():
        out.append(s.pop())

    return out[:-1]

bds1 = 'a+b/c^d-e'          # abcd^/+e-
bds2 = '(a+b)*c-(d+e)/f'    # ab+c*de+f/-

print(bds1, ''.join(solve(bds1)))
print(bds2, ''.join(solve(bds2)))

 

三、根据后缀表达式求值

def solve5(bds):
    '''根据后缀表达式求值'''
    jishuan = {
        '^': lambda x,y: x**y,
        '*': lambda x,y: x*y,
        '/': lambda x,y: x/y,
        '+': lambda x,y: x+y,
        '-': lambda x,y: x-y
    }
    s = Stack()
    for x in bds:
        if x in '^*/+-':
            num2, num1 = s.pop(), s.pop()
            r = jishuan[x](float(num1), float(num2))
            s.push(r)
        else:
            s.push(x)

    return s.pop()

bds1 = '2+9/3^2-5'         # 2932^/+5-   -2
bds2 = '(1+2)*3-(4+5)/6'   # ab+c*de+f/- 7.5

print(bds1, '=', solve5(solve(bds1)))
print(bds2, '=', solve5(solve(bds2)))

#print(bds1, '=', eval(bds1))
print(bds2, '=', eval(bds2))

 

时间: 2024-11-13 07:55:47

python 逆波兰式的相关文章

SPOJ Transform the Expression 逆波兰式算法题解

把带括号的一般正常的算式,转换成逆波兰式. 输入和输出如下例子: Input: 3 (a+(b*c)) ((a+b)*(z+x)) ((a+t)*((b+(a+c))^(c+d))) Output: abc*+ ab+zx+* at+bac++cd+^* 总结规律是很困难的事情,总结好就能很快解决: 1 字母直接放结果 2  '('入栈 3 ')' 出栈到'(',然后出栈'(' 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Program

C语言实现逆波兰式实例_C 语言

复制代码 代码如下: #include<stdio.h>#include<string.h> typedef struct{char s[20][20];int top;}SQ; void copystr(char *a,char *b){    int i=0;    do    {        b[i]=a[i];        i++;    }    while(a[i]!='\0');    b[i]='\0';} void voidSQ(SQ *s){    s-&g

PHP使用逆波兰式计算工资的方法_php技巧

本文实例讲述了PHP使用逆波兰式计算工资的方法.分享给大家供大家参考.具体如下: 将一个普通的中序表达式转换为逆波兰表达式的一般算法是: 首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入逆波兰 式的栈S2(空栈),S1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束.可指定其他字符,不一定非#不可.从中缀式的左端 开始取字符,逐序进行如下步骤: (1)若取出的字符是操作数,则分析出完整的运算数,该操作数直接送入S2栈:若取出的是运算符,并

逆波兰式与表达式求值

何为波兰式?何为逆波兰式? 如何与表达式求值联系起来? 波兰式.逆波兰式是数据结构和编译原理里面提到的知识点,我们平时的运算式都是这样的 2 + 3 * (5 - 1)-10(中缀表达式),这样表达式易于阅读和计算,但是对于计算机这样就有点懵逼了. 前缀表达式: 比如2 + 3 * (5 - 1)这个表达式的前缀表达式为+ 2 * 3 - 5 1来表示  波兰表达式 中缀序表达式:比如 2 + 3 * (5 - 1)-10 后缀表达式:比如2 + 3 * (5 - 1)用逆波兰式来表示则是:2

python实现逆波兰计算表达式的方法

  这篇文章主要介绍了python实现逆波兰计算表达式的方法,较为详细的分析了逆波兰表达式的概念及实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下 逆波兰表达式又叫做后缀表达式.在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示.波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法.按此方法,每一运算符都置于其运算对象之后,故称为后缀表示. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

算法题:逆波兰表达式(数学逆波兰表达式和交并集逆波兰表达式)

一.前言 在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示 法也称为中缀表示.每一运算符都置于其运算对象之后,称为后缀表达式,后缀表达式又叫做逆波兰表达式. 它的优势在于只用两种简单操作,入栈和出栈就可以搞定任何普通表达式的运算.其运算方式如下:如果当前 字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表 达式扫描完后,栈里的就是结果. 二.一般算法 将一个普通的中序表达式转换为逆波兰表达式 的一般算法是: (1)首先构

Python列表推导式的使用方法_python

1.列表推导式书写形式: [表达式 for 变量 in 列表]    或者  [表达式 for 变量 in 列表 if 条件] 2.举例说明: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- li = [1,2,3,4,5,6,7,8,9]print [x**2 for x in li] print [x**2 for x in li if x>5] print dict([(x,x*10) for x in li]) print  [ (

Selenium2+python自动化38-显式等待(WebDriverWait)

前言: 在脚本中加入太多的sleep后会影响脚本的执行速度,虽然implicitly_wait()这种方法隐式等待方法一定程度上节省了很多时间. 但是一旦页面上某些js无法加载出来(其实界面元素经出来了),左上角那个图标一直转圈,这时候会一直等待的. 一.参数解释 1.这里主要有三个参数: class WebDriverWait(object):driver, timeout, poll_frequency 2.driver:返回浏览器的一个实例,这个不用多说 3.timeout:超时的总时长

python ip正则式_python

ip正则式为:r'(([12][0-9][0-9]|[1-9][0-9]|[1-9])\.){3,3}([12][0-9][0-9]|[1-9][0-9]|[1-9])' 以下为一个示例 #-*- coding:utf-8 -*- import re def ip(): '验证IP的正则式' def match_group(p): s = '''211.210.209.108 gan ffad1.210.2.108 d ffad1.210.2.109afa''' com = re.compile