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

Question

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

If it's a job interview question, as the original poster says it is, then it is unlikely the candidate will be expected to produce out of a hat things like shunting yard algorithms, recursive descent parsers, converting infix to postfix et al all within a maximum of half an hour perhaps, and pull it off.

No. They are probably testing your ability to handle things like strings, testing them for things like operators {*,/,+,-}, left and right parentheses, digits etc and seeing if you can write code / pseudocode to evaluate the example expression they have provided, not an all-singing, all-dancing application.

On the other hand if you want an example of how to write an evaluator for strings like "(1+3 * ( 5 / 4))" that returns a numeric result, here are some C++ / Java examples.

Answer 2

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.