0

I'm trying to build an arbitrary precision calculator. I represent numbers in linked lists (one node is a single digit), and I want to store them in a stack. However, I can't seem to figure out how to break the mathematical expression received as a string apart while keeping the right mathematical operations order.

For example, if the inserted expression is 6*8-2+8-8*9/4, I'll represent numbers as linked lists and insert them into a stack, and insert the operators into a different stack, and then I want to pop the arguments for each calculations and push the result again, and so on until I get the final result.

My question is, how can I implement this and still follow the mathematical operations order?

smci
  • 32,567
  • 20
  • 113
  • 146
mrpink121
  • 191
  • 1
  • 3
  • 13
  • A common way to do this is to first convert the expression to [RPN](https://en.wikipedia.org/wiki/Reverse_Polish_notation) using Dijkstra's [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm) – PM 2Ring Jan 03 '17 at 14:09
  • First, use standard library's shlex to tokenize, then come up with grammar and implement a parser. I find shift reduce parser the simplest to understand and implement. I did a toy project recently on this -- shreducers on github. – jbasko Jan 03 '17 at 14:12
  • Please see this question and good replies. http://stackoverflow.com/questions/28256/equation-expression-parser-with-precedence – rajah9 Jan 03 '17 at 15:33

1 Answers1

0

you could try using eval?

eval("6*8-2+8-8*9/4")

This would give you 36

EDIT:

If eval isn't feasible, maybe try operator to convert the string operators to mathematical ones:

import operator
operations = {
    '+' : operator.add,
    '-' : operator.sub,
    '*' : operator.mul,
    '/' : operator.div,
    '%' : operator.mod,
    '^' : operator.xor
}

Then maybe you could loop through the string and evaluate it that way? (I'll have a think about the looping part now and edit my answer if I get anything good)

RichSmith
  • 900
  • 5
  • 11
  • I wish. It's a college project and I'm required to do it exactly as i wrote it. – mrpink121 Jan 03 '17 at 14:02
  • Ah fair enough, I'll have a think and update my answer if I come up with anything useful :) – RichSmith Jan 03 '17 at 14:03
  • Thank you kind sir! – mrpink121 Jan 03 '17 at 14:04
  • Doing it this way is ok if you evaluate stuff in strict left-to-right order, but it gets tricky if you want to use the usual mathematical precedence rules and you need to handle parenthesized expressions. – PM 2Ring Jan 03 '17 at 14:12
  • @PM2Ring yeah I'm sure there is a better solution to my answer, I'm going to have a read through of the things you mentioned in your comment earlier, looks really interesting and useful to know! :) – RichSmith Jan 03 '17 at 14:14