How to write an evaluator for a string like "(1+3 * ( 5 / 4)) and get a numeric result.

Question

hi, this is a interview question i am confused about its solution, i am thinking that i need stacks to push and pop these operators and operands, but do i need two stacks, one for operator and one for operands? or would just one stack do?i think we need two stacks but is there any way to solve using one stack?

also i am bit confused how would this work, each time i get an operator i would pop two of my topmost operands and push the result in the operand stack

the preferance is brackets first,then divide,multioply and last subtraction and then addition

but how to check when to pop the two operands and do the necessary arthimetic operation?

Answer 1

well. it's parsing. it's quite a work.. a freind of mine has wrote a very impressive program, exactly for that, that open one varible equations as well, all in OOP. very neat.

basically, make a list of operators order, start with the brackets.

find the most internals: search for the first ) [close] then from there search back for the first ( [open].

now you have your internal phrase without brackets. now search for * for example, find the number behind and the number after, now replace this phrase (e.g. 514*354.25) with it answer.

this is the most primitive way to do this.. just gave you a start. for the reset you probably have no choice by using you brain :P

(if you are interested in my friend's project just say so)

Answer 2

You are parsing expressions with a recursively defined structure. A simple option is to write what's called a recursive decent parser:

See http://en.wikipedia.org/wiki/Recursive%5Fdescent%5Fparser

It's straight forward once you understand that the top level "parse expression" routine has to call itself to parse its constituent expressions like EXPRESSION + EXPRESSION. What you'll end up with is a tree of operator nodes with expression trees for operands.

You could also use a tool like Bison. Bison is a "compiler compiler" which builds a table driven parser for a language given a grammar. (Bison is pretty old school: Search for "parser generator" for more info.)

Answer 3

Take a look at the shunting yard algorithm.

The shunting yard algorithm is a method for parsing mathematical equations specified in infix notation. It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard.

Answer 4

I have implemented this in very few lines of code using the boost spirit parser. It worked out really well for me in a variety of contexts. (http://spirit.sourceforge.net/)

To elaborate: the spirit parser allows you to construct a grammar in standardish BNC and creates a AST tree from the expression - you can then trivially walk this tree (in case of an interpretive environment) and calculate the expression. A short learning curve for spirit and BNC will be required but this is certainly easier than rolling your own expression evaluator

Answer 5

Itay,

Your answer was probably downvoted because it will result in a slow and memory-intensive evaluator. You basically create a list of all separate items (values and operators) and then do a lot of scanning backwards and forwards to find items that belong together to create new items.

The other suggestions (recursive descent, shunting) can evaluate the expression in just a single pass and store temporary values on a stack.

Another advantage: a recursive descent parser results in clean and simple code, if you can wrap your head around the recursive part of it.

This is a sensitive issue to me: I support some software that uses your method to create a parse tree and only then evaluates the parse tree to arrive at a single answer. The software is amazingly slow at calculations and the source code is quite unwieldy. But the replacement evaluator, based on a parser generator, is coming together!

Answer 6

This problem is called a recursive descent parser. There may be other forms of canonical solution, I'm sure there is - maybe dozens of correct approaches. David Eck has a recursive descent parser posted online with source code and explanation. Google should turn up thousands of useful resources and those should be also looked into at dmoz and your favorite search engine.