Infix Expression Evaluation
July 20, 2012
One of the most fundamental operations in computing is to evaluate an arithmetic expression, observing the precedences and associativities of the operators. For instance, given the expression 3+4*5, the multiplication is performed first, then the addition, giving a result of 23. Parentheses may change the order of evaluation, so that (3+4)*5 is 35. Today’s task is to write a program that takes as input a string containing an arithmetic expression and returns as output the result of evaluating that expression.
The usual approach to this task is to write a parser that identifies each element of the expression, evaluates them, and combines them into a solution. The parser is driven by a grammar that enumerates the various elements; the usual grammar for arithmetic expressions is:
expr -> term | expr + term | expr - term
term -> factor | term * factor | term / factor
factor -> number | ( expr )
Here -> and | are metasymbols of the grammar, +, -, *, /, ( and ) are operator literals, and expr, term, factor and number are operands; it’s not shown above, but a number is and integer consisting of either 0 or a sequence of digits not starting with 0, with an optional leading - sign. Blanks anywhere in the expression, even between the digits of a number, are ignored.
The evaluator consists of a set of mutually recursive functions that each recognize one metastatement of the grammar, plus a driver that accepts an input string and returns the result, all organized as dictated by the grammar.
As an example, consider the input string (3+4)*5. The driver passes the input to a function that recognizes expressions. Since the metastatement for expressions expects a term, that function immediately passes the input to a function that recognizes terms. Then, since the metastatement for terms expects a factor, that function immediately passes the input to a function that recognizes factors. That functions recognizes the opening parenthesis and calls the function that recognizes expressions to evaluate what is inside the parenthesis. Again, the expression metastatement looks for a term, and the term metastatement looks for a factor, and the factor metastatement looks for a number, which it finds, so it returns 3 to the term metatstatment, which returns 3 to the expression metastatement. Then the expression metastatement recognizes the + sign and goes next to the 4. The expression metastatement calls the term metastatement, which calls the factor metastatement, which identifies the 4 and passes it back to the term metastatement, which passes it back to the expressions metastatement, which adds it to 3 giving a result of 7. Now the expression metastatement is satisfied because the next input character is not a +, - or expression, so it returns the 7 to the expression that was called within the parentheses of the factor metastatement. The next character is a closing parenthesis, so the factor metastatement is complete, and passes back the 7 to the term metastatement. Now the next character is *, which is recognized by the term metastatement, which passes the remainder of the input string, the 5 character, to the factor metastatement. Now the factor metastatement recognizes the number 5 and returns it to the term metastatement, which multiplies it by 7 producing a result of 35. The result is passed back to the expression metastatement, which recognizes that the expression is complete, so it passes the result 35 back to the driver function, which outputs the result. Whew! Aren’t you glad you have a computer to do all of that work for you?
Your task is to write a function that evaluates an infix arithmetic expression. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to write a function to evaluate mathematical expressions. […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/20/programming-praxis-infix-expression-evaluation/ for a version with comments):
import Control.Applicative ((<$), (<$>)) import Text.Parsec import Text.Parsec.Expr import Text.Parsec.Language import Text.Parsec.Token eval :: String -> Either ParseError Double eval = parse expr "" where expr = buildExpressionParser table term term = parens mondrian expr <|> (read <$> many1 (lexeme mondrian digit)) table = [ [prefix "-" negate] , [binary "*" (*), binary "/" (/) ] , [binary "+" (+), binary "-" (-) ] ] prefix name fun = Prefix (fun <$ symbol mondrian name) binary name fun = Infix (fun <$ symbol mondrian name) AssocLefthttp://pastebin.com/iJKwEbNJ
a tough one for me, took a good 5 hours to get it bug free.
Python 3.3
import operator as op import re op = {'+':op.add, '-':op.sub, '*':op.mul, '/':op.floordiv} def expr(token): value = term(token) while token and token[0] in ('+', '-'): value = op[token.pop(0)](value, term(token)) return value def term(token): value = factor(token) while token and token[0] in ('*', '/'): value = op[token.pop(0)](value, factor(token)) return value def factor(token): if token[0].isdigit(): value = int(token.pop(0)) elif token[0] == '-': token.pop(0) value = -factor(token) elif token[0] == '(': token.pop(0) value = expr(token) if token[0] != ')': raise SyntaxError("Expected ')', got '%s'" % token[0]) else: token.pop(0) else: SyntaxError("Expected number or '(', got '%s'" % token[0]) return value def calc(expression): try: token = re.findall(r'(\d+|.)', ''.join(expression.strip().split())) value = expr(token) if token: raise SyntaxError("Extra tokens: %s" % token) except SyntaxError as ex: print("Syntax Error:", str(ex)) else: return value[…] Pages: 1 2 […]
(I’ve heard rumors of lenders charging higher rates).
Before you fix and flip a property for profit, you should determine
if you have enough funds to see a rehabbing project
through. The tuition of my seminars ranges from $395 to $695 depending on the venue.
Such programs at Spanish schools are a solution for health care workers who
are looking to learn the language quickly. In essence, there can be
no better way of learning English than learning some other language, because the act of learning will cause
you to analyze the origin and construction of
your own language. The more you do it, the more quickly your mind will be able to convert words into the new
language.