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.

About these ads

Pages: 1 2

7 Responses to “Infix Expression Evaluation”

  1. [...] today’s Programming Praxis exercise, our goal is to write a function to evaluate mathematical expressions. [...]

  2. 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) AssocLeft
    
  3. phil said

    http://pastebin.com/iJKwEbNJ

    a tough one for me, took a good 5 hours to get it bug free.

  4. Mike said

    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
    
  5. Pablo said

    (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.

  6. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: