Nerd Paradise
Home
About
Puzzles
Math
Programming
Origami
Japanese
MSPaint
Home > Programming > How to Parse Mathematical Expressions

How to Parse Mathematical Expressions

Update: This script is now hosted on GitHub and maintained by Louis Fisch and includes new features.


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 value

print 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")

You are visitor #003714
Get notified about new posts by following the newfangled twitter account.
Best viewed with
© 1999 Nerd Paradise