前言:
目前兄弟们对“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语言中缀表达式转后缀表达式并求值