0

I'm implementing a calculator in C ++ that respects the priorities of parentheses. I am trying to use std :: string :: find_last_of to find the last occurrence of ( and std :: string :: find to find the first occurrence of ). Once that is done, I reckon the content of the extracted substring and continuing with the rest of the string. For example:

1 + 1 * (9 * (11-1 + 2))

I find the last occurrence of (, the first of ) and calculating 11-1 + 2. And so it continues. Is this the right approach to this problem or is there something better? Thank you.

Local Hero
  • 493
  • 2
  • 7
  • 20

2 Answers2

3

You can use Reversed Polish Notation:
You will need to convert the expression into reversed polish notation and then implement a stack based algorithm to pop and push to the final answer.

Have a look at the Shunting- Yard algorithm here: To convert the expression into RPN.
https://en.wikipedia.org/wiki/Shunting-yard_algorithm

Also Have a look at
Writing a simple equation parser
For help to implement the stack, have a look here:
C++ Calculator using Stacks and Queues

Community
  • 1
  • 1
novice
  • 545
  • 3
  • 16
0

One of the standard approaches to this problem consists of 2 steps:

1) Convert your expression to Reverse Polish notation: https://en.wikipedia.org/wiki/Reverse_Polish_notation using Shunting-yard algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm

2) Evaluate converted expression using stack.

The another way to do this:

1) Easy step: Write Backus–Naur Form of your expressions https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

And after you have 2 options:

2a) Build Finite-State Machine: https://en.wikipedia.org/wiki/Finite-state_machine (exists a lot of tools to do this: ANTLR, ...).

2b) Recursive descent method: https://en.wikipedia.org/wiki/Recursive_descent_parser

SashaMN
  • 708
  • 5
  • 16