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

代码中采用了三步实现算术表达式的解析:

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: selfimpr
    blog: http://blog.csdn.net/lgg201
    mail: [e-mail]
    company: http://www.dartfar.com
    function: 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 list
def getLast(l):
    if l:
        return l[len(l) - 1]

def parseElement(expression):
    '''
    author: selfimpr
    blog: http://blog.csdn.net/lgg201
    mail: [e-mail]
    company: http://www.dartfar.com
    function: parse a string expression to list
    '''
    result = []
    cur = ""
    for index in range(len(expression)):
        ch = expression[index]
        if numberable.__contains__(ch):
            cur += ch
        elif signable.__contains__(ch):
            if cur:
                result.append(float(cur))
                cur = ""
            if ["*", "/"].__contains__(ch) and getLast(result) == ch:
                result[len(result) - 1] *= 2
            elif ["+", "-"].__contains__(ch) /
            and ["+", "-", "*", "/", "%", "**", "//", "(", ")"].__contains__(getLast(result)) /
            and not ["+", "-", "*", "/", "%", "**", "//", "(", ")"].__contains__(expression[index + 1]):
                cur += ch
            else:
                result.append(ch)
        else:
            raise Exception, "Error"
    if cur:
        result.append(float(cur))
    return result

def priority(sign1, sign2):
    '''
    author: selfimpr
    blog: http://blog.csdn.net/lgg201
    mail: [e-mail]
    company: http://www.dartfar.com
    function: check priority between two arguments
    '''
    return priorities[sign1] > priorities[sign2]
    

def changeToSuffix(expression):
    '''
    author: selfimpr
    blog: http://blog.csdn.net/lgg201
    mail: [e-mail]
    company: http://www.dartfar.com
    function: 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() == "(":
                        break
                    suffix.append(signStack.pop())
                signStack.push(element)
        else:
            raise Exception("Unsupport sign or number")
    while not signStack.empty():
        suffix.append(signStack.pop())
    return suffix

def calc(a, b, sign):
    '''
    author: selfimpr
    blog: http://blog.csdn.net/lgg201
    mail: [e-mail]
    company: http://www.dartfar.com
    function: calculate result a sign b
    '''
    if sign == "+":
        return b + a
    elif sign == "-":
        return b - a
    elif sign == "*":
        return b * a
    elif sign == "/":
        return b / a
    elif sign == "**":
        return b ** a
    elif sign == "//":
        return b // a
    else:
        raise Exception("Unsupport sign: %s" % sign)

def account(expression):
    '''
    author: selfimpr
    blog: http://blog.csdn.net/lgg201
    mail: [e-mail]
    company: http://www.dartfar.com
    function: 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()