c++ - 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

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.