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.

Improve this question
6
  • 2
    What about (1+1)*(2+2)? Commented Jan 19, 2016 at 9:21
  • the priority is the same so it is irrelevant, right? Commented Jan 19, 2016 at 9:23
  • 2
    The best way is to use a stack! Commented Jan 19, 2016 at 9:23
  • @LucaPizzamiglio do you have some example? Commented Jan 19, 2016 at 9:24
  • @LocalHero here you can find a pdf explaining how to use queues and stacks. Stack can be used to evaluate the correctness and the value of this type of expressions Commented Jan 19, 2016 at 9:30

2 Answers 2

Reset to default
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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.