A function that evaluates simple mathematical expressions.

  • (2 Pages)
  • +
  • 1
  • 2

20 Replies - 1291 Views - Last Post: 29 March 2019 - 05:16 AM Rate Topic: -----

#1 martymcfly   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 09-July 16

A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 10:25 AM

I am trying to write a function that evaluates simple mathematical expressions (only four operations). I used stack and vector to do this. But stack operations don't behave as I expect. I couldn't find the cause. I am open to different solutions.

The function should take a string like this:

"5 * 44 + 3 / 2 * 4 - 12"

And return the result as a double.

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <cstdlib>

using namespace std;

vector<string> split(const std::string& str, char delim = ' ')
{
    vector<string> elements;
    stringstream ss(str);
    string token;
    while (getline(ss, token, delim)) {
        elements.push_back(token);
    }

    return elements;
}


double evaluate(string operation)
{
    vector<string> values = split(operation, ' ');
    stack<string> result_stack;
    double result = 0;

    for(unsigned int i = 0; i < values.size(); i++){
        if(values[i] == "*"){
            double mini_result = stod(result_stack.top()) * stod(values[i+1]);
            result_stack.pop();
            i++;
            result_stack.push(to_string(mini_result));
        }
        else if(values[i] == "/"){
            double mini_result = stod(result_stack.top()) / stod(values[i+1]);
            result_stack.pop();
            i++;
            result_stack.push(to_string(mini_result));
        }
        else{
            result_stack.push(values[i]);
        }
    }

    for(unsigned int i = 0; i<result_stack.size(); i++){
        if(result_stack.top() == "-"){
            result_stack.pop();
            result = stod(result_stack.top()) - result;
            result_stack.pop();
        }
        else if(result_stack.top() == "+"){
            result_stack.pop();
            result += stod(result_stack.top());
            result_stack.pop();
        }
        else{
            result += stod(result_stack.top());
            result_stack.pop();
        }
    }

    return result;

}




int main()
{

    cout<<evaluate("5 * 44 + 3 / 2 * 4 - 12");
}




Before the second for loop, values in the result_stack should be like this for this example. "12 | - | 6 | + | 220" . And the returning value should be 214.

But before the second for loop, stack contains only "12 | - | 6" values. "+" and "220" values are not there. Some extra pops occur which I don't expect.

stack content should be like this for this example
Posted Image

This post has been edited by martymcfly: 27 March 2019 - 10:39 AM


Is This A Good Question/Topic? 0
  • +

Replies To: A function that evaluates simple mathematical expressions.

#2 jimblumberg   User is online

  • member icon

Reputation: 5703
  • View blog
  • Posts: 17,481
  • Joined: 25-December 09

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 11:26 AM

It appears that in your addition and subtraction loop that the loop counter i is getting out of sync with the size of the stack. You've removed items from the stack, thereby reducing it's size but the loop counter doesn't know this. Perhaps you might want to consider a while() loop using the stack.empty() function?

Jim
Was This Post Helpful? 3
  • +
  • -

#3 martymcfly   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 09-July 16

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 11:37 AM

:) Thank you very much. Even diplaying the stack to see what is wrong. I made same mistake and thought the problem was in the first loop. Thanks again.

This post has been edited by Skydiver: 27 March 2019 - 12:41 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 1
  • +
  • -

#4 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6818
  • View blog
  • Posts: 23,196
  • Joined: 05-May 12

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 12:43 PM

Also +1 to martymcfly for putting together a well written question that shows he's tried to do his homework before posting the question!
Was This Post Helpful? 1
  • +
  • -

#5 jimblumberg   User is online

  • member icon

Reputation: 5703
  • View blog
  • Posts: 17,481
  • Joined: 25-December 09

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 12:52 PM

I located the problem by running the program with my debugger single stepping through the functions and watching the variables as I stepped. I noticed that in that last loop that it appeared to be terminating early. The difficult part was determining why.

Jim
Was This Post Helpful? 1
  • +
  • -

#6 martymcfly   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 09-July 16

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 01:08 PM

Actually this is not a homework. But thank you :) Is there something wrong with putting last status of the code. (corrected version) Maybe some people want to see.

This post has been edited by martymcfly: 27 March 2019 - 01:11 PM

Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6818
  • View blog
  • Posts: 23,196
  • Joined: 05-May 12

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 01:12 PM

By homework, I meant that you tried to do as much analysis of the problem by yourself. You included the behavior you were expecting to see, as well an the behavior that you were actually seeing.

You were following the key elements of: How To Ask Questions The Smart Way
Was This Post Helpful? 0
  • +
  • -

#8 martymcfly   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 09-July 16

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 01:16 PM

Okay, I understand. Thank you again.
Was This Post Helpful? 0
  • +
  • -

#9 jimblumberg   User is online

  • member icon

Reputation: 5703
  • View blog
  • Posts: 17,481
  • Joined: 25-December 09

Re: A function that evaluates simple mathematical expressions.

Posted 27 March 2019 - 02:14 PM

Quote

Is there something wrong with putting last status of the code.

Nope not a problem at all, unless you did it at work (check with your boss).


Jim
Was This Post Helpful? 0
  • +
  • -

#10 martymcfly   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 09-July 16

Re: A function that evaluates simple mathematical expressions.

Posted 28 March 2019 - 04:05 AM

Thanks to @jimblumberg
Corrected version of the code:

vector<string> split(const std::string& str, char delim = ' ')
{
    vector<string> elements;
    stringstream ss(str);
    string token;
    while (getline(ss, token, delim)) {
        elements.push_back(token);
    }

    return elements;
}

long double evaluate(string operation)
{
    vector<string> values = split(operation, ' ');
    list<string> result_list;
    long double result = 0;

    for(unsigned int i = 0; i < values.size(); i++){
        if(values[i] == "*"){
            double mini_result = stod(*result_list.begin()) * stod(values[i+1]);
            result_list.pop_front();
            i++;
            result_list.push_front(to_string(mini_result));
        }
        else if(values[i] == "/"){
            double mini_result = stod(*result_list.begin()) / stod(values[i+1]);
            result_list.pop_front();
            i++;
            result_list.push_front(to_string(mini_result));
        }
        else{
            result_list.push_front(values[i]);
        }
    }

    result_list.reverse();

    while(!result_list.empty()){
        if(*result_list.begin() == "-"){
            result_list.pop_front();
            result -= stod(*result_list.begin());
            result_list.pop_front();
        }
        else if(*result_list.begin() == "+"){
            result_list.pop_front();
            result += stod(*result_list.begin());
            result_list.pop_front();
        }
        else{
            result += stod(*result_list.begin());
            result_list.pop_front();
        }
    }

    return result;
}



Was This Post Helpful? 0
  • +
  • -

#11 jimblumberg   User is online

  • member icon

Reputation: 5703
  • View blog
  • Posts: 17,481
  • Joined: 25-December 09

Re: A function that evaluates simple mathematical expressions.

Posted 28 March 2019 - 08:38 AM

Is there a particular reason you switched from the std::stack to the std::list and to the long double?

            result -= stod(*result_list.begin());

Do you realize that you are doing an implicit cast to a long double in this code (and all similar instances)? If you want to use the long double then you really should be using the correct conversion function for the type.


Oh, and that is an incomplete program, no headers and no main().


Jim
Was This Post Helpful? 0
  • +
  • -

#12 martymcfly   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 09-July 16

Re: A function that evaluates simple mathematical expressions.

Posted 28 March 2019 - 12:36 PM

:sweatdrop: :bigsmile: :) you love code review.
About using list instead of stack:
I have 300000 inputs to evaluate, realized some results are not correct. This is because of subtraction was not processing in right order. The subtraction and summing process(2nd loop) should have done in opposite order of the stack. Because of that, I used list instead.

About long double:
When i see wrong results; I thought, at some point, the result variable may not be enough to store the value and this may cause wrong result. But I suppose this is not required for the inputs I have. I can use double instead.

Incomplete program?
Is it really necessary to put the complete program? Header files which should be included, parameter and return value are so obvious. But I can add them, not a problem.


Quote

If you want to use the long double then you really should be using the correct conversion function for the type.

I didn't understand here, can you explain in detail?
Was This Post Helpful? 0
  • +
  • -

#13 jimblumberg   User is online

  • member icon

Reputation: 5703
  • View blog
  • Posts: 17,481
  • Joined: 25-December 09

Re: A function that evaluates simple mathematical expressions.

Posted 28 March 2019 - 01:42 PM

Quote

Is it really necessary to put the complete program?

A complete program helps because then someone can compile and run the program without making assumptions. For example the program in the OP failed to compile with my compiler because of a missing include file. Also that program had at least one extra header file.

Quote

Header files which should be included, parameter and return value are so obvious.

Not as obvious as it seems. Not including a necessary include file and not using the correct parameters are one of the many "simple" causes of program failure.

Quote

About long double:
When i see wrong results; I thought, at some point, the result variable may not be enough to store the value and this may cause wrong result. But I suppose this is not required for the inputs I have. I can use double instead.

This is a sign of throwing code at the problem, a very poor way to troubleshoot problems. Learning to use your tools, the debugger in this case, is a much better and often easier method of troubleshooting.

Quote

Quote

If you want to use the long double then you really should be using the correct conversion function for the type.

I didn't understand here, can you explain in detail?


You are using stod() to convert the value in your string to a double which was then implicitly casted to a long double to be stored in your variable. You should have been using stold() to convert the string to a long double instead of stod(). This is another reason that knowing the return value, and parameter types for functions is necessary to determine why the program is not working correctly.

Quote

About using list instead of stack:
I have 300000 inputs to evaluate, realized some results are not correct.

This is probably not a problem with using a stack but a problem in your implementation. Why did you find it necessary to reverse the list? A stack probably would have already been it the correct order.

Also do you realize that a list is probably not as efficient as a stack, queue, or vector for most real world operations?


Jim
Was This Post Helpful? 1
  • +
  • -

#14 martymcfly   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 09-July 16

Re: A function that evaluates simple mathematical expressions.

Posted 28 March 2019 - 02:00 PM

Quote

This is probably not a problem with using a stack but a problem in your implementation. Why did you find it necessary to reverse the list? A stack probably would have already been it the correct order.


I had to reach items in opposite order, is it possible to do it in stack? Maybe using queue is more appropriate for this. I tried to take elements from the list in opposite order but couldn't. So I reversed the list, does it cause increasing cost?

Quote

Also do you realize that a list is probably not as efficient as a stack, queue, or vector for most real world operations?

Why? :)
Was This Post Helpful? 0
  • +
  • -

#15 jimblumberg   User is online

  • member icon

Reputation: 5703
  • View blog
  • Posts: 17,481
  • Joined: 25-December 09

Re: A function that evaluates simple mathematical expressions.

Posted 28 March 2019 - 02:56 PM

Quote

Why?

Because a list is spread out in memory where the other containers are usually in contiguous regions and thereby reduce cache misses that can plague lists. See this link for more information.

Quote

I had to reach items in opposite order, is it possible to do it in stack?

A stack is usually already in the opposite order compared to a list. By the way you should be able to access any element of a list not just the first or the last. A standard stack only gives you access to the "top" item.

Quote

Maybe using queue is more appropriate for this.

Well a queue gives you access to both the front and the back, so maybe.

Quote

So I reversed the list, does it cause increasing cost?

Well it is another operation that iterates over the whole container, so yes.

And don't forget that most containers give you both forward iterators and reverse iterators.

Normally the first container you should consider is std::vector since it is usually the fastest container and it gives you random access to all members of the container.

Jim
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2