龙空技术网

Python数据结构与算法08:基本结构:栈的应用之表达式转换(下)

挂可挂 101

前言:

目前兄弟们对“c语言中缀表达式转后缀表达式并求值”大致比较注意,兄弟们都需要分析一些“c语言中缀表达式转后缀表达式并求值”的相关知识。那么小编也在网摘上网罗了一些对于“c语言中缀表达式转后缀表达式并求值””的相关内容,希望你们能喜欢,你们快快来了解一下吧!

注:本文如涉及到代码,均经过Python 3.7实际运行检验,保证其严谨性。

本文阅读时间约为9分钟。

接下来讨论通用的中缀表达式转换为后缀表达式的算法,以及如何使用Python程序来实现中缀表达式转换为后缀表达式这一过程。


算法


通用的中缀转后缀表达式的算法思考

在后缀表达式中,操作符的出现顺序运算次序一致,因此会出现操作符调整顺序的情况。

中缀表达式转换为后缀表达式的处理过程中,操作符比操作数要晚输出。所以在程序扫描到对应的第二个操作数之前,需要先把操作符保存起来。

这些保存起来的操作符当中,由于优先级的规则,有的操作符可能需要反转次序输出。这种保存需求和反转特性,使得我们考虑用栈这种数据结构来保存暂时未处理的操作符。

比如A + B * C中,"+"虽然先出现,但是优先级不如后面的"*",因此它要等到"*"操作符处理完成之后,才能再进行处理。

关于操作符的优先级,由于有括号强制优先级的情况,所以不一定是优先级更高的操作符排在前面,而是要看操作符实际的优先顺序。比如(A+B)*C中,“+”的优先级就要高于“*”,所以这个中缀表达式的后缀形式是AB+C*。对于这种情况,程序的算法又该如何解决呢?

解决方法是,程序扫描到左括号时,标记下来,其后出现的操作符的优先级要得到提高,当扫描到对应的右括号时,就可以马上输出这个优先级得到提高的操作符。


通用的中缀转后缀表达式的算法总结

想通了上述的各种细节,就可以对通用的中缀转后缀表达式的算法做一个总结了:

在从左到右逐个字符扫描中缀表达式的过程中,采用一个栈来暂存未处理的操作符。

由于栈的LIFO(后进先出)的特性,栈顶的操作符就是最近暂存进去的,当遇到一个新的操作符,就需要跟栈顶的操作符先比较优先级,再决定如何处理。


通用的中缀转后缀表达式的算法流程详解

注:后面的算法描述中,约定中缀表达式是由空格隔开的一系列单词(token,即最小的一个词法单位)构成。操作符的单词token包括*/+-(),操作数的单词token则是单字母标识符A、B、C等。

首先,创建空栈opstack用于暂存操作符,空列表postfixList用于保存后缀表达式。用字符串形式的中缀表达式转换为单词(token)作为元素构成的列表。

例如,"A + B * C"字符串利用字符串方法string.split(" ")转换成由操作数和操作符构成的列表['A', '+', 'B', '*', 'C']。 然后,再从左至右扫描中缀表达式单词列表,会有以下几种情况:

如果单词token是操作数,则直接添加到后缀表达式列表postfixList的末尾;如果单词token是左括号“(”,则压入opstack栈顶(所谓压入栈顶,就是将元素入栈);如果单词token是右括号“)”,则反复弹出opstack栈顶操作符(所谓弹出栈顶,就是将元素移除出栈),加入到输出列表postfixList的末尾,直到碰到左括号为止;如果单词是操作符“*/+-”,则压入opstack栈顶——压入之前,要比较其与opstack栈当前的栈顶操作符的优先级。如果当前栈顶的操作符的优先级高于或等于它,则要反复弹出栈顶的操作符,将栈顶的操作符输出并加入到列表postfixList的末尾,直到opstack栈顶的操作符的优先级低于它为止。把只装操作符的栈想象成一堆盘子,上面的是栈顶,下面的是栈底,这里的要求是,栈底的操作符的优先级必须小于栈顶的操作符。

接着,中缀表达式单词列表扫描结束后,把opstack栈中的所有剩余操作符依次弹出,添加到输出列表postfixList的末尾。

最后,把输出列表postfixList再用join方法使其转化为字符串形式的后缀表达式,算法结束。


具体实现的代码如下:

# 中缀表达式转后缀表达式的程序。class Stack:    def __init__(self):        self.items = []            def isEmpty(self):        return self.items == []    def push(self, item):        self.items.append(item)    def pop(self):        return self.items.pop()    def peek(self):        return self.items[len(self.items)-1]    def size(self):        return len(self.items)def infixToPostfix(infixexpr):    """    infixexpre:一个字符串类型的中缀表达式,操作数与操作符之间都由空格" "隔开。    如"A+B*C+D"是错误的输入,"A + B * C + D"才是正确的输入。    """        # 下面连续6行是用一个字典记录操作符优先级。    prec = {}    prec["*"] = 3    prec["/"] = 3    prec["+"] = 2    prec["-"] = 2    prec["("] = 1    opStack = Stack()  # 创建一个名为opStack的空栈。    postfixList = []    tokenList = infixexpr.split()  # 解析表达式到单词列表。    for token in tokenList:        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":  #操作数。            postfixList.append(token)        elif token == '(':  # 碰到左括号“(”,直接输出。            opStack.push(token)        elif token == ')':  # 碰到右括号“)”,不停地弹出来。            topToken = opStack.pop()            while topToken != '(':                postfixList.append(topToken)                topToken = opStack.pop()        else:  # 碰到操作符也是不停地弹出,直到栈顶的操作符优先级比自己低。            while (not opStack.isEmpty()) and \            (prec[opStack.peek()] >= prec[token]):                postfixList.append(opStack.pop())            opStack.push(token)    while not opStack.isEmpty():            postfixList.append(opStack.pop())  # 操作符。    return " ".join(postfixList)  # 合成后缀表达式字符串。         print(infixToPostfix("A + B * C + D"))  <<<A B C * + D +

To be continued.

标签: #c语言中缀表达式转后缀表达式并求值