11

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?

Ray
  • 777
  • 2
  • 8
  • 22
  • 1
    I'm too lazy to try to answer your question, but it might be worth having a look at B. Stroustrup's "The C++ Programming Language". His example program is a desk calculator. –  Oct 17 '09 at 05:13
  • Expressions like the one in your question are often best modelled with trees, rather than with stacks. Good luck! – Carl Norum Oct 17 '09 at 05:15
  • 1
    This is a commonly asked question on SO. Here is one: http://stackoverflow.com/questions/1151127/evaluating-mathematical-expressions – Greg Hewgill Oct 17 '09 at 05:16
  • @everyone thanks for the input, ill search along with these helps and also how it can be modeled with trees – Ray Oct 17 '09 at 05:28
  • 1
    Original and most authoritative SO compilers questions (and this is a compilers question): http://stackoverflow.com/questions/1669/learning-to-write-a-compiler . Code golf questions with very short solution under various constraints: http://stackoverflow.com/questions/928563/code-golf-evaluating-mathematical-expressions http://stackoverflow.com/questions/1384811/code-golf-mathematical-expression-evaluator-full-pemdas http://stackoverflow.com/questions/1538964/code-golf-reverse-polish-notation-postfix-evaluator – dmckee --- ex-moderator kitten Oct 17 '09 at 12:52

6 Answers6

11

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.

Robert Groves
  • 7,574
  • 6
  • 38
  • 50
7

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_descent_parser

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

Matt
  • 343
  • 1
  • 2
  • 7
4

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.

AndyUK
  • 3,933
  • 7
  • 42
  • 44
1

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

Elemental
  • 7,365
  • 2
  • 28
  • 33
0

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)

Letterman
  • 4,076
  • 5
  • 29
  • 41
  • I'm not the down-voter and feel your solution is okay. However it is the most naive solution and standard libraries (see my answer) and standard algorithms (Matt + Robert) do exist for this class of problem. – Elemental Oct 19 '09 at 08:57
  • yeah i know, but if the guy is asking this, he better start from the basics, does he not? and i have wrote this is the most naive. (btw, this is NOT how my friend's done it). – Letterman Oct 19 '09 at 12:24
0

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.

Nicholas Jordan
  • 638
  • 3
  • 6