Do not feed the troll
The Forum > Front Page Posts > How to Parse Mathematical Expressions
 Blake Webmaster2082 Posts11 Vigeo 11:4 - 0.50.58738.715 days ago The following code snippet is a parser of simple mathematical expressions. It recognizes the four basic mathematical operations and parentheses. You can also pass in a variable table as a dictionary of strings to numbers. "pi" and "e" are also recognized. The parser is more or less a stream with a Peek capability. Each nested function call will parse out some sort of expression such as addition/subtraction or division/multiplication while moving through the string stream. These function calls are nested in the inverse of order of operations (because the deepest nested operations as being done first). Each function returns a float, but can be modified to return something else. For example, each function could instead return an image and this can easily be modified to create an equation renderer. Or instead of a float or an image, it can return an instance of some sort of class with methods to interpret its inner components. Following that approach, with some tweaks, this could easily become your own programming language. The possibilities are quite endless. Anyways, here's the code. Have fun tweaking it: # A really simple expression evaluator supporting the # four basic math functions, parentheses, and variables. class Parser:    def __init__(self, string, vars={}):        self.string = string        self.index = 0        self.vars = {            'pi' : 3.141592653589793,            'e' : 2.718281828459045            }        for var in vars.keys():            if self.vars.get(var) != None:                raise Exception("Cannot redefine the value of " + var)            self.vars[var] = vars[var]        def getValue(self):        value = self.parseExpression()        self.skipWhitespace()        if self.hasNext():            raise Exception(                "Unexpected character found: '" +                self.peek() +                "' at index " +                str(self.index))        return value        def peek(self):        return self.string[self.index:self.index + 1]        def hasNext(self):        return self.index < len(self.string)        def skipWhitespace(self):        while self.hasNext():            if self.peek() in ' \t\n\r':                self.index += 1            else:                return        def parseExpression(self):        return self.parseAddition()        def parseAddition(self):        values = [self.parseMultiplication()]        while True:            self.skipWhitespace()            char = self.peek()            if char == '+':                self.index += 1                values.append(self.parseMultiplication())            elif char == '-':                self.index += 1                values.append(-1 * self.parseMultiplication())            else:                break        return sum(values)        def parseMultiplication(self):        values = [self.parseParenthesis()]        while True:            self.skipWhitespace()            char = self.peek()            if char == '*':                self.index += 1                values.append(self.parseParenthesis())            elif char == '/':                div_index = self.index                self.index += 1                denominator = self.parseParenthesis()                if denominator == 0:                    raise Exception(                        "Division by 0 kills baby whales (occured at index " +                        str(div_index) +                        ")")                values.append(1.0 / denominator)            else:                break        value = 1.0        for factor in values:            value *= factor        return value        def parseParenthesis(self):        self.skipWhitespace()        char = self.peek()        if char == '(':            self.index += 1            value = self.parseExpression()            self.skipWhitespace()            if self.peek() != ')':                raise Exception(                    "No closing parenthesis found at character "                    + str(self.index))            self.index += 1            return value        else:            return self.parseNegative()        def parseNegative(self):        self.skipWhitespace()        char = self.peek()        if char == '-':            self.index += 1            return -1 * self.parseParenthesis()        else:            return self.parseValue()        def parseValue(self):        self.skipWhitespace()        char = self.peek()        if char in '0123456789.':            return self.parseNumber()        else:            return self.parseVariable()        def parseVariable(self):        self.skipWhitespace()        var = ''        while self.hasNext():            char = self.peek()            if char.lower() in '_abcdefghijklmnopqrstuvwxyz0123456789':                var += char                self.index += 1            else:                break                value = self.vars.get(var, None)        if value == None:            raise Exception(                "Unrecognized variable: '" +                var +                "'")        return float(value)        def parseNumber(self):        self.skipWhitespace()        strValue = ''        decimal_found = False        char = ''                while self.hasNext():            char = self.peek()                        if char == '.':                if decimal_found:                    raise Exception(                        "Found an extra period in a number at character " +                        str(self.index) +                        ". Are you European?")                decimal_found = True                strValue += '.'            elif char in '0123456789':                strValue += char            else:                break            self.index += 1                if len(strValue) == 0:            if char == '':                raise Exception("Unexpected end found")            else:                raise Exception(                    "I was expecting to find a number at character " +                    str(self.index) +                    " but instead I found a '" +                    char +                    "'. What's up with that?")            return float(strValue)        def evaluate(expression, vars={}):    try:        p = Parser(expression, vars)        value = p.getValue()    except Exception as (ex):        msg = ex.message        raise Exception(msg)        # Return an integer type if the answer is an integer     if int(value) == value:        return int(value)        # If Python made some silly precision error     # like x.99999999999996, just return x + 1 as an integer     epsilon = 0.0000000001    if int(value + epsilon) != int(value):        return int(value + epsilon)    elif int(value - epsilon) != int(value):        return int(value)        return valueprint evaluate("1 + 2 * 3")print evaluate("(1 + 2) * 3")print evaluate("-(1 + 2) * 3")print evaluate("(1-2)/3.0 + 0.0000")print evaluate("1 + pi / 4")print evaluate("(a + b) / c", { 'a':1, 'b':2, 'c':3 })print evaluate("(x + e * 10) / 10", { 'x' : 3 })print evaluate("1.0 / 3 * 6")print evaluate("(1 - 1 + -1) * pi")print evaluate("pi * e") [Quote] [Link]
 ooh, Python. I wonder that if I tweaked it enough, I could get it to recognize prefix notation and other s-expy stuff. [Quote] [Link]