用栈解析算术表达式[Python版]

dryu999

　　代码中采用了三步实现算术表达式的解析:
　　1. 将算术表达式(字符串)转换成一个列表parseElement方法
　　2. 将列表表示的算术表达式转换成后缀表达式changeToSuffix
　　3. 计算后缀表达式的结果
　　这里我是为了方便, 就写了个parseElement, 不想那方法写到后面却把自己绕住了, 可以想象一个带自增, 位, 逻辑, 算术的表达式的数值提取是多么的复杂...
　　parseElement自己感觉是一个比较失败的方法, 所以从一个普遍的角度来分析以下算术表达式的解析:
　　以(A + B) * C / D ** E + F * G为例
　　第一部分: 将中缀表达式(上面就是, 具体去查有关前缀, 中缀, 后缀表达式)
　　这一步需要一个栈用来保存运算符, 一个字符串用来保存输出的后缀表达式
　　符号栈: signStack
　　后缀表达式: result
　　过程: 读取表达式中每个元素(数字或运算符, 我的parseElement意在解决这个问题, 却做的不成功)
　　原则:
　　1. 操作数直接输出到result
　　2. (直接进栈
　　3. )出栈直到遇到一个"("(注意: 这里"("必须出栈), 中间出栈的元素按出栈顺序输出到result
　　4. 其他运算符, 检查栈顶元素, 如果栈顶比当前运算符优先级高或相同(优先级相同, 按顺序执行)则先将栈顶出栈, 再入栈. 如果当前元素优先级高, 则直接入栈.
　　操作过程的状态变化
　　signStack |result |current char
　　------------------------------------------------------
　　( | |(
　　( |A |A
　　(, + | |+
　　( |AB |B
　　|AB+ |)
　　* | |*
　　* |AB+C |C
　　/ |AB+C* |/
　　/ |AB+C*D |D
　　/, **|AB+C*D |**
　　/, **|AB+C*DE |E
　　+|AB+C*DE**/ |+
　　+|AB+C*DE**/F |F
　　+, * |AB+C*DE**/F |*
　　|AB+C*DE**/FG*+ |G
　　唉, 不太美观啊..
　　第二部分: 计算后缀表达式(AB+C*DE**/FG*+)
　　这一步需要一个栈用来保存操作数
　　值栈
　　过程: 读取后缀表达式中每个元素
　　原则:
　　1. 操作数直接进栈
　　2. 遇到一个运算符则出栈两个, 计算结果再进栈
　　操作过程的状态变化
　　stack |current char
　　------------------------------------------------------
　　A |A
　　A, B  |B
　　(A+B)  |+
　　(A+B), C |C
　　(A+B)*C |*
　　((A+B)*C), D |D
　　((A+B)*C), D, E |E
　　((A+B)*C), (D**E) |**
　　(((A+B)*C)/(D**E))|/
　　(((A+B)*C)/(D**E)), F |F
　　(((A+B)*C)/(D**E)), F, G |G
　　(((A+B)*C)/(D**E)), (F*G) |*
　　((((A+B)*C)/(D**E))+(F*G)) |+
　　还是不很美观哈, 呵呵, 逗号把元素隔开, 应该还是可以看的比较清晰了...呵呵..
　　'''Created on 2009-9-4@author: selfimpr'''signable = ["+", "-", "*", "/", "%", "(", ")"]numberable = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "."]signs = ["+", "-", "*", "/", "%", "**", "//"]priorities = {"(": 9, ")": 9, "**": 7, "*": 5, "/": 5, "%": 5, "//": 5, "+": 3, "-": 3}class Stack(object):'''author: selfimprblog: http://blog.csdn.net/lgg201mail: lgg860911@yahoo.com.cncompany: http://www.dartfar.comfunction: This is a general stack, use to do the sign and number's temp store'''def __init__(self):self.datas = []def push(self, data):self.datas.append(data)def pop(self):return self.datas.pop()def peek(self):if self.datas:return self.datas[len(self.datas) - 1]def size(self):return len(self.datas)def empty(self):return len(self.datas) < 1#a bit function, return last element of listdef getLast(l):if l:return l[len(l) - 1]def parseElement(expression):'''author: selfimprblog: http://blog.csdn.net/lgg201mail: lgg860911@yahoo.com.cncompany: http://www.dartfar.comfunction: parse a string expression to list'''result = []cur = ""for index in range(len(expression)):ch = expression[index]if numberable.__contains__(ch):cur += chelif signable.__contains__(ch):if cur:result.append(float(cur))cur = ""if ["*", "/"].__contains__(ch) and getLast(result) == ch:result[len(result) - 1] *= 2elif ["+", "-"].__contains__(ch) /and ["+", "-", "*", "/", "%", "**", "//", "(", ")"].__contains__(getLast(result)) /and not ["+", "-", "*", "/", "%", "**", "//", "(", ")"].__contains__(expression[index + 1]):cur += chelse:result.append(ch)else:raise Exception, "Error"if cur:result.append(float(cur))return resultdef priority(sign1, sign2):'''author: selfimprblog: http://blog.csdn.net/lgg201mail: lgg860911@yahoo.com.cncompany: http://www.dartfar.comfunction: check priority between two arguments'''return priorities[sign1] > priorities[sign2]def changeToSuffix(expression):'''author: selfimprblog: http://blog.csdn.net/lgg201mail: lgg860911@yahoo.com.cncompany: http://www.dartfar.comfunction: change a infix expression to suffix(Notice: the infix is a list, you can parse a infix expression to list by previous function names parseElement)'''if not isinstance(expression, list) or not list or isinstance(expression[0], list):raise Exception("expression must be a not-null list and first element must be a number")suffix = []signStack = Stack()for element in expression:if isinstance(element, float):suffix.append(element)elif ["+", "-", "*", "/", "%", "**", "//", "(", ")"].__contains__(element):if element == "(":signStack.push(element)elif element == ")":while not signStack.empty()/and signStack.peek() != "(":suffix.append(signStack.pop())signStack.pop()else:while not signStack.empty()/and not priority(element, signStack.peek()):if signStack.peek() == "(":breaksuffix.append(signStack.pop())signStack.push(element)else:raise Exception("Unsupport sign or number")while not signStack.empty():suffix.append(signStack.pop())return suffixdef calc(a, b, sign):'''author: selfimprblog: http://blog.csdn.net/lgg201mail: lgg860911@yahoo.com.cncompany: http://www.dartfar.comfunction: calculate result a sign b'''if sign == "+":return b + aelif sign == "-":return b - aelif sign == "*":return b * aelif sign == "/":return b / aelif sign == "**":return b ** aelif sign == "//":return b // aelse:raise Exception("Unsupport sign: %s" % sign)def account(expression):'''author: selfimprblog: http://blog.csdn.net/lgg201mail: lgg860911@yahoo.com.cncompany: http://www.dartfar.comfunction: calculate a suffix expression (Notice: it must a list)'''if not isinstance(expression, list) or not list or isinstance(expression[0], list):raise Exception("expression must be a not-null list and first element must be a number")numberStack = Stack()for element in expression:if isinstance(element, float):numberStack.push(element)else:numberStack.push(calc(numberStack.pop(), numberStack.pop(), element))return numberStack.pop()