Calculate math from string // c++

[Kamjam66xx]

Hey guys. Im working out my own algorithm for takinga math problem as written in a string, and answering it. 

 

My test problem is:

(((1 + 2) + (2/1)) 2) + 2^5

 

Still got a lot of thinking it up. But does anyone see anything fatally wrong with my path, or am i on the right path?

 

This is my first "complex" algorithm im trying to think up and then code. Thanks  

 

 

Edit: Really just after if my algorithm makes sense for order of operation with '(' && ')'

 

The "simpleMath()" will take care of '^' and all that. Im still thinking up how to take multiplication with no sign and make that work, but i dont expect any problems thinking that up. 

[mariushm]

go from last character to first

memorize the last detected ) character position

stop where a ( character is found

run this function  with only the text between ( )

replace ( xxx ) with the result 

if replacement was done go back to the end of the string, because you may need to determine last  ) character again  for example in case of a phrase like  1+ ( ( 5*2) + 3)

when there's no parantheses found in the string, you switch to basic parsing ... ignore all characters but digits, arithmetic signs (+,-,*,/,^) and you have pairs of numbers and the operator ... tokenize or whatever the expression is ... go from last to first and handle the priority operators first  (^ , * , / , \ , whatever) then repeat with the rest

 

it can be done in a fancier way with recursivity but...  if you're interested and I'm not getting bored, I may try to make an example code for you in php  (c like syntax so should be easy to adapt)

 

 

[Kamjam66xx]

34 minutes ago, mariushm said:

 

That would be great to compare against. Im going to have a function that turns..

 

This: 1 (1-2)

And turns it into..

This: 1*(1-2) 

 

Before

 

But if there is any merit to creating it entirely my own and showing that to a possible future employer, i want to go that route. I dont want to outright copy anything.

 

[Mira Yurizaki]

Ah, I did something like this as one of the projects for a class I took way back when. I still think it's one of the scariest things I've accomplished.

 

The thing that made it all work though was the tokens. The tokens were functions that took an argument or two and spit out the result. And it was made in such a way that the argument could be another token.

 

I forgot how I handled order of operations though. I probably had it do multiple passes.

[Kamjam66xx]

10 minutes ago, M.Yurizaki said:

Ah, I did something like this as one of the projects for a class I took way back when. I still think it's one of the scariest things I've accomplished.

 

The thing that made it all work though was the tokens. The tokens were functions that took an argument or two and spit out the result. And it was made in such a way that the argument could be another token.

 

I forgot how I handled order of operations though. I probably had it do multiple passes.

I dropped out of highschool. Im doing it for me, then to build a ui later and add as my first useful program to my portfolio.

 

Ive been watching tv more than working on it. But heres my ugly notes and reasoning. Some of it is wrong, so i tried again. Some of it is also probably not the most efficient too.

 

I might be the only person who can read it lol. Will post the code when im done too, if it works out. This is my second month of c++ and programming.

[Franck]

Is this a homework or real life scenario ?

[Unimportant]

13 hours ago, Kamjam66xx said:

Hey guys. Im working out my own algorithm for takinga math problem as written in a string, and answering it.

Don't reinvent the wheel. The first step is to write a lexical analyzer, or lexer.

With that as a search term you can find lots of articles online discussing the canonical ways of doing things.

[Franck]

9 minutes ago, Unimportant said:

Don't reinvent the wheel. The first step is to write a lexical analyzer, or lexer.

With that as a search term you can find lots of articles online discussing the canonical ways of doing things.

Yes that's it, i was looking for the word for it. Lexer is what he need.

Here a very power working solution you can base yourself on : https://github.com/sheetsync/NCalc

It also support many language and not only numbers but dates and more complicated stuff

[Kamjam66xx]

36 minutes ago, Unimportant said:

Don't reinvent the wheel. The first step is to write a lexical analyzer, or lexer.

With that as a search term you can find lots of articles online discussing the canonical ways of doing things.

I looked it up briefly. Ill take a deeper look later. But it looks basically like what im doing... kindof

[Kamjam66xx]

This will sound stupid... 

But i cant figure out the simplest part.

 

Getting a single line entered by the user, and shoving it into a std::deque.

Help?

[fizzlesticks]

1 hour ago, Kamjam66xx said:

Getting a single line entered by the user

std::getline

 

Quote

std::deque

Should pretty much not be used. Unless you plan on allowing equations that are millions of characters long std::vector will be better in every way (even push_front.)

[Kamjam66xx]

21 hours ago, fizzlesticks said:

std::getline

 

Should pretty much not be used. Unless you plan on allowing equations that are millions of characters long std::vector will be better in every way (even push_front.)

I fixed it, and why not a deque? 

Edit: *my problem was taking it character by character and puting it into a deque && also having single line input without asking the user to do anything special*

 

My code might look terrible, i havent been able to dig through advanced c++ books yet.

 

ill use sstream to convert str to int. Then if "+" then do whatever. Im going really slow probably for my first program. If i wasnt trying to think up this algorithm and combating by bad grammer and bugs im sure id be farther. But im at 173 lines of code right now.

 

Edit: just noticed begin() istead of the const cbegin(), oops.

[fizzlesticks]

1 hour ago, Kamjam66xx said:

why not a deque? 

std::deques have tons of overhead and are inefficient in how they store data compared to a std::vector. For a smallish program like you'll never be able to notice the difference but it's something to keep in mind for other things.

 

Quote

std::deque<std::string> uMathCont(128);

...loop code...

std containers have constructors that can do this work for you. 

std::deque<std::string> uMathCont(std::cbegin(uMathInput), std::cend(uMathInput));

However when you iterate over the input string you're iterating over characters not strings, so it should really be std::deque<char>.

edit: if you're using a c++17 compatible compiler (which you should be!) you can let the compiler figure that out for you and just write 
std::deque deq(std::cbegin(uMathInput), std::cend(uMathInput));

 

std::endl isn't just a way to write a newline character, it also forces a flush which can have a huge impact on performance (again not really noticeable in a small program like this.) 

For more a bit more info on that you can check out these 2 videos

https://www.youtube.com/watch?v=GMqQOEZYVJQ

https://www.youtube.com/watch?v=lHGR_kH0PNA

 

Lastly when posting code please copy/paste into code tags instead of taking a picture.

[Razbit]

My approach would be something along these lines:

1) parse the string starting from the "main" operator, save to a tree data structure

2) walk the tree from the leaves up, calculating each node from its two children

3) when at the top, done.

 

e.g. 2 * (1 - 4)

main operator *, operands 2 and (1-4)

add the * to the root node of the tree

add 2 as the other child of the * node

parse the parantheses, creating a new "-" child for the "*" node

add 1 and 4 as its children

 

now the tree should be like this

      *

     / \

   -    2

  / \

1  4

 

walking the tree from the bottom up:

1) 1 - 4 = -3, thus the tree:

      *

     / \

  -3    2

2) -3 * 2 = -6, thus the tree:

     -6

 

done.

 

On a side note, a reverse polish notation calculator would be a lot easier to implement. Actually this is the reason first powerful calculators from e.g. HP used RPN instead of the more usual infix notation: the code needed for parsing parentheses took up a large portion of the calculators' memory, thus taking space from more advanced functions.

 

My implementation for an infix calculator actually transformed the expression into RPN and then calculated it.

see https://github.com/Razbit/it5/tree/master/stack

[Kamjam66xx]

19 hours ago, Razbit said:

 

Thanks, i appreciate it. I kept restarting from a blank slate and trying a bunch of different methods. 

 

Cleaning up how i code and reading books on sql, virtual machines, ai, css, matlab, data science, and algorithms. So i temporarily abandoned it, BECAUSE i felt like all of my approaches were too complicated. 

 

Is that just how software engineering always feels? Lol i enjoy it, but still.

I guess ill just write my terribly coded calculator.

[Razbit]

Thinking out an algorithm is not an easy task. Even though a calculator might seem simple, there is quite a lot more to it than you'd think on the first glance.. Point being, you should not settle with whatever first comes to your mind (even if it worked ). Trying to find alternate solutions is always a good idea!

[MyName13]

Why not just use the shunting yard algorithm?