0

Can anyone show me a good algorithm for multiplication,division,addition and subtraction using stacks?I've seen quite a lot of algorithms,but they all have the same problem.For example,if the expression is 5+4*2 , the program sees that * needs to be done first , so it puts everything on the stacks so it looks like this:

2
4      *
5      +
val    op


while (!op.empty())
{
int num1 = val.top();
char operator = op.top();
val.pop();
int num2 = val.top();
val.pop();op.pop();
stack.push(calculate(num2,num1,sign));
//where calcu late is a function that returns the result of that operation
}

But if the expression looks like this:3 - 4*4 + 5*3,the stack will be:

15
16     +
3      -
val    op

so it will do 15 + 16 - 3 , which is 28 , instead of :3 - 16 + 15 = 2. Can anyone provide me a good algorithm using stacks?Thanks!

Botje
  • 26,269
  • 3
  • 31
  • 41
  • 1
    "Using stacks" is just an implementation detail. You need an expression parser that is aware of operator precedence. – Botje Nov 17 '20 at 08:59
  • 1
    The technique you're looking for is called the [shunting yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm). This is the closest dup I could find: [Convert from an infix expression to postfix (C++) using Stacks](https://stackoverflow.com/questions/12684086/convert-from-an-infix-expression-to-postfix-c-using-stacks) – Botje Nov 17 '20 at 09:02
  • @Botje So , first i have to convert my expression from infix to postfix , and after that i can do an algorithm? –  Nov 17 '20 at 10:41
  • The outcome of the shunting yard algorithm is a stack of numbers and operators in the correct order. You can then trivially evaluate it. Your second example will become `3 4 4 * - 5 3 * +`, for example. – Botje Nov 17 '20 at 10:44
  • @Botje so i'll have a string stack with my post-fix expression , and then i can evaluate it –  Nov 17 '20 at 10:48
  • It can be a stack of strings if you insist, I would use a custom `NumberOrOp` type that can be either a number or an op. – Botje Nov 17 '20 at 10:59
  • @botje sorry for many questions , but do i really have to transform it into a post-fix expression to be calculated?Isn't there another way? –  Nov 17 '20 at 12:29
  • The other way involves writing an precedence-aware expression parser, as the linked Wikipedia article shows. There are tons of examples of expression parsers on StackOverflow. My favorite is the [lemon expression parser](http://freshmeat.sourceforge.net/articles/lemon-parser-generator-tutorial) – Botje Nov 17 '20 at 12:33

0 Answers0