The Forum > Front Page Posts > How to Parse Mathematical Expressions
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") |
![[avatar]](/uploads/avatars/1_871929099.png)
![[avatar]](/uploads/avatars/6777_820129650.png)
So looking at this, it looks like it's a bit inefficient, doing the call for every single operation even if said operation is not to be found. Which is fine for something so simple, but I found this when looking for how to parse equations, and it seems to be able to be able to do it with fewer function calls. It might be interesting for people. (Plus he writes an almost complete Python parser by the end, it looks like.) Edit: Also, since that follows the method for producing a parse tree, it's still quite applicable for drawing an equation. |
![[avatar]](/uploads/avatars/21_793087726.jpeg)
The Forum > Front Page Posts > How to Parse Mathematical Expressions