服务器之家

服务器之家 > 正文

浅析前缀,后缀,中缀表达式转化求值问题

时间:2020-12-21 23:51     来源/作者:Python之王

浅析前缀,后缀,中缀表达式转化求值问题

算法,一门既不容易入门,也不容易精通的学问。

上次介绍如何利用栈实现中缀表达式求值,如果我是出题官,当然要考前缀,后缀,中缀表达式相互转换,然后就变成了利用栈实现前缀和后缀表达式求值。

前缀,后缀,中缀表达式相互转换及其运算,可以说是计算机考研的一个重点。

首先看下面所示表格:

浅析前缀,后缀,中缀表达式转化求值问题

  • 注意:前序表达式和后序表达式是没有扩号

这篇文章有对应的图解:https://mp.weixin.qq.com/s/NRbFXZAXEUeXhKKYY7CReg

中缀表达式转前缀表达式求值

中缀表达式转前缀表达式的规则:

1、反转输入字符串,如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”, 

2、从字符串中取出下一个字符 

  2.1.如果是操作数,直接输出 

  2.2.如果是“)”,压入栈中 

  2.3.如果是运算符但不是“(”,“)”,则不断循环进行以下处理 

    2.3.1.如果栈为空,则此运算符进栈,结束此步骤 

    2.3.2.如果栈顶是“)”,则此运算符进栈,结束此步骤 

    2.3.2.如果此运算符与栈顶优先级相同或者更高,此运算符进栈,结束此步骤 

    2.3.4.否则,运算符连续出栈,直到满足上述三个条件之一,然后此运算符进栈 

  2.4、如果是“(”,则运算符连续出栈,直到遇见“)”为止,将“)”出栈且丢弃之 

3、如果还有更多的字符串,则转到第2步 

4、不在有未处理的字符串了,输出栈中剩余元素 

5、再次反转字符串得到最终结果 

经过上面的步骤,得到的输出既是转换得到的前缀表达式。

前缀表达式的计算方法:对前缀表达式从后向前扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。直至从右到左扫描完毕整个前缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为前缀表达式的计算结果。

上面的过程使用数据结构栈来实现,具体代码如下

''

@Author:Runsen 

@WeChat:RunsenLiu  

@微信公众号:Python之王 

@CSDN:https://blog.csdn.net/weixin_44510615 

@Github:https://github.com/MaoliRUNsen 

@Date:2020/12/17 

''

import re 

 

class Stack(): 

    def __init__(self): 

        self.items = [] 

 

    def push(self, item): 

        return self.items.append(item) 

 

    def pop(self): 

        return self.items.pop() 

 

    def size(self): 

        return len(self.items) 

 

    def peek(self): 

        return self.items[len(self.items) - 1] 

 

    def display(self): 

        print(self.items) 

 

def infix_to_prefix(s): 

    prec = { 

        '*': 3, 

        '/': 3, 

        '+': 2, 

        '-': 2, 

        '(': 4, 

        ')': 1 

    } 

 

    a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('请输入中缀表达式:')) 

    prefix = [] 

 

    for x in a[::-1]: 

        if re.match('[0-9]', x): 

            #操作数,直接输出 

            prefix.append(x) 

        else

            #如果是“)”,压入栈中 

            if x == ')'

                s.push(x) 

            elif x == '('

                while True

                    i = s.pop() 

                    if i == ')'

                        break 

                    else

                        prefix.append(i) 

            else

                if s.size() > 0 and prec[x] <= prec[s.peek()]: 

                    prefix.append(s.pop()) 

                s.push(x) 

    for _ in range(s.size()): 

        prefix.append(s.pop()) 

    return prefix[::-1] 

     

def cal_prefix(s, prefix): 

    # 思路:对前缀表达式从后向前扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。 

    # 直至从右到左扫描完毕整个前缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为前缀表达式的计算结果。 

    for x in prefix[::-1]: 

        if re.match('[0-9]', x): 

            s.push(x) 

        else

            a2 = int(s.pop()) 

            a1 = int(s.pop()) 

            if x == '*'

                a = a1 * a2 

            elif x == '/'

                a = a2 / a1 

            elif x == '+'

                a = a1 + a2 

            else

                a = a2 - a1 

            s.push(a) 

    return s.pop() 

 

if __name__ == '__main__'

    s = Stack() 

    prefix = infix_to_prefix(s) 

    print('前缀表达式:', prefix) 

    prefix_val = cal_prefix(s, prefix) 

    print('前缀表达式计算结果:', prefix_val) 

 

请输入中缀表达式:2*3/(2-1)+3*(4-1) 

前缀表达式: ['+''*''2''/''3''-''2''1''*''3''-''4''1'

前缀表达式计算结果: 15 

请输入中缀表达式:9+(3-1*2)*3+10/2 

前缀表达式: ['+''+''9''*''-''3''*''1''2''3''/''10''2'

前缀表达式计算结果: 17 

中缀表达式转换为后缀表达式求值

中缀表达式转后缀表达式的规则:

1.遇到操作数,直接输出;

2.栈为空时,遇到运算符,入栈;

3.遇到左括号,将其入栈;

4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出;

5.遇到其他运算符’+”-”*”/’时,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈;

6.最终将栈中的元素依次出栈,输出。

经过上面的步骤,得到的输出既是转换得到的后缀表达式。

后缀表达式的计算方法:对后缀表达式从前向后扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。直至从右到左扫描完毕整个后缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为后缀表达式的计算结果。

上面的过程使用数据结构栈来实现,具体代码如下:

''

@Author:Runsen 

@WeChat:RunsenLiu 

@微信公众号:Python之王 

@CSDN:https://blog.csdn.net/weixin_44510615 

@Github:https://github.com/MaoliRUNsen 

@Date:2020/12/17 

''

import re 

 

class Stack(): 

    def __init__(self): 

        self.items = [] 

 

    def push(self, item): 

        return self.items.append(item) 

 

    def pop(self): 

        return self.items.pop() 

 

    def size(self): 

        return len(self.items) 

 

    def peek(self): 

        return self.items[len(self.items) - 1] 

 

    def display(self): 

        print(self.items) 

 

 

def infix_to_postfix (s): 

    prec = { 

        '*': 3, 

        '/': 3, 

        '+': 2, 

        '-': 2, 

        '(': 1, 

        ')': 4 

    } 

 

    a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('请输入中缀表达式:')) 

    postfix = [] 

 

    for x in a: 

        if re.match('[0-9]', x): 

            # 操作数,直接输出 

            postfix.append(x) 

        else

            # 如果是“(”,压入栈中 

            if x == '('

                s.push(x) 

            elif x == ')'

                while True

                    i = s.pop() 

                    if i == '('

                        break 

                    else

                        postfix.append(i) 

            else

                if s.size() > 0 and prec[x] <= prec[s.peek()]: 

                    postfix.append(s.pop()) 

                s.push(x) 

    for _ in range(s.size()): 

        postfix.append(s.pop()) 

    return postfix 

 

 

def cal_postfix (s, postfix): 

    for x in postfix: 

        if re.match('[0-9]', x): 

            s.push(x) 

        else

            a1 = int(s.pop()) 

            a2 = int(s.pop()) 

            if x == '*'

                a = a1 * a2 

            elif x == '/'

                a = a2 / a1 

            elif x == '+'

                a = a1 + a2 

            else

                a = a2 - a1 

            s.push(a) 

    return s.pop() 

 

 

if __name__ == '__main__'

    s = Stack() 

    postfix = infix_to_postfix(s) 

    print('后缀表达式:', postfix) 

    postfix_val = cal_postfix (s, postfix) 

    print('后缀表达式计算结果:', postfix_val) 

 

 

请输入中缀表达式:2*3/(2-1)+3*(4-1) 

['2''3''*''2''1''-''/''3''4''1''-'

后缀表达式: ['2''3''*''2''1''-''/''3''4''1''-''*''+'

后缀表达式计算结果: 15 

请输入中缀表达式:9+(3-1*2)*3+10/2 

后缀表达式: ['9''3''1''2''*''-''3''*''10''2''/''+''+'

后缀表达式计算结果: 17 

其实此题是Leetcode第150题,逆波兰表达式求值。

根据 逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

示例 1: 

 

输入: ["2""1""+""3""*"

输出: 9 

解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9 

示例 2: 

 

输入: ["4""13""5""/""+"

输出: 6 

解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6 

前缀表达式转中缀表达式

从右往左开始,取出一个操作符和操作符右边的两个数进行计算,并将计算的结果放过去,直到计算结束。以前缀表达式+/*23-21*3-41为例,将其转换为中缀表达式:

(1)取出-、4、1,计算并将结果放回得到+/*23-21*3(4-1);

(2)取出*、3、(4-1),计算并将结果放回得到+/*23-21(3*(4-1));

(3)取出-、2、1,计算并将结果放回得到+/*23(2-1)(3*(4-1));

(3)取出*、2、3,计算并将结果放回得到+/(2*3)(2-1)(3*(4-1));

(4)取出/、(2*3)、(2-1),计算并将结果放回得到+((2*3)/(2-1))(3*(4-1));

(5)取出+、((2*3)/(2-1))、(3*(4-1)),计算将结果放回得到((2*3)/(2-1))+(3*(4-1)),计算结束,显然计算结果为15。

后缀表达式转中缀表达式从左向右开始,取出一个操作符和操作符左边的两个数进行计算,并将计算的结果放过去,直到计算结束,以后缀表达式23*21-/341-*+为例,将其转换为中缀表达式:(1)取出2、3、*,计算并将结果放回得到(2*3)21-/341-*+;

(2)取出2,1,-,计算并将结果放回得到(2*3)(2-1)/341-*+;

(3)取出(2*3)、(2-1)、/,计算并将结果放回得到((2*3)/(2-1))341-*+;

(4)取出4,1,-,计算并将结果放回得到((2*3)/(2-1)) 3(4-1)*+;

(5)取出3,(4-1),*,计算并将结果放回得到((2*3)/(2-1)) 3*(4-1)+;

(6)取出((2*3)/(2-1)),3*(4-1),+,计算并将结果放回得到((2*3)/(2-1)) + 3*(4-1),显然计算结果为15。

本文已收录 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100

原文地址:https://mp.weixin.qq.com/s/qzhpg8FUckSoOMCh_l99pg

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
返回顶部