Is using string as expression possible in c++?

[PainterGuy]

hello everyone,

okay. i am stuck here now. i was experimenting and though why can not i enter an expression at once. you understand what i am trying to achieve. i am newbie to programming so achieving this is beyond me so you tell me in the output "((7+7)*9)/9" is a string. is there any way to make if function as a math expression? tell me please if this is possible.

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int main()

{
 	
 	string exp;
 	
 	cout << "enter the expression = ";
 	cin >> exp;
 	
 	cout << exp << endl;
	
	return 0;	
}

here's a example output:

enter the expression = ((7+7)*9)/9
((7+7)*9)/9
Press any key to continue . . .

cheers

 

[Borg]

If I understand you correctly, you would like to take the string expression and process it mathematically. Yes, it's possible but you would have to parse and process all of your possible operators. Try starting out with a simple program without any braces with operators of equal precedence and work your way up from there. For example, can you figure out how to process the following equation with a program?

2 * 6 / 3

 

[PainterGuy]

If I understand you correctly, you would like to take the string expression and process it mathematically. Yes, it's possible but you would have to parse and process all of your possible operators. Try starting out with a simple program without any braces with operators of equal precedence and work your way up from there. For example, can you figure out how to process the following equation with a program?

2 * 6 / 3

Many thanks Borg.

Yes you understood it rightly. This is what I'm trying to do.

Sorry, I don't know how to process (or parse, as you say) the given equation? Could you help me out with it please?

Cheers

 

[chiro]

hello everyone,

okay. i am stuck here now. i was experimenting and though why can not i enter an expression at once. you understand what i am trying to achieve. i am newbie to programming so achieving this is beyond me so you tell me in the output "((7+7)*9)/9" is a string. is there any way to make if function as a math expression? tell me please if this is possible.

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int main()

{
 	
 	string exp;
 	
 	cout << "enter the expression = ";
 	cin >> exp;
 	
 	cout << exp << endl;
	
	return 0;	
}

here's a example output:

enter the expression = ((7+7)*9)/9
((7+7)*9)/9
Press any key to continue . . .

cheers

Hey painterguy.

I'll talk briefly about the general way to do this and a specific way that will do the job for you and isn't as complicated.

The general way to do this problem is to use grammars and parse trees to break up your expression into tokens and have a grammar verify that your syntax is correct. Basically in a nut-shell you take your expression (your string that you enter and print out with your cout command) and you break it up into tokens and then you do stuff with those tokens.

The best way I think you should go about doing this is to use a binary tree and implement a routine that calculates your expression. I know you probably haven't come across b-trees (ie the binary trees, this is the nickname that they have) so I'll give them in a nutshell.

A binary tree is basically a tree where each node has a left and a right node which is a tree itself. The leaves of the tree are the nodes that don't have any children. So the simplest tree is simply a tree with one node. I'll give a specific example:

Lets say you want to put (9+7)*3 into a tree form. Your root node would have an "*" state and your left child of the root node would be a "+". Your left child of the plus would be a "9" and your right child would be a "3". Going back to to the right child of the "*" node you would have a "3" in your right child.

What happens is that if you evaluate your tree "left to right" you end up calculating your value which is (9+7)*3 = 48. Here is how it works step by step:

You call your evaluate function
It recursively goes down to the leaves
When it finds leaves it looks at the operation and performs it for the left child and the right branch.
After it has done it for the leaves it works its way up the tree until it gets to the root and finishes.

So in your example tree I posted above it finds a leaf at 9 and the node above it is a + so it calculates 9 + 7 and returns that. It works its way up the tree and takes the 16 it calculated and applies the "*" operation to the right branch with 16 and what ever is calculated for the right branch, which since it is also a leaf just returns the value 3. So when the process gets back to the root it ends up evaluating the two branches with the "*" operator and the two values 16 and 3 and gives 48.

The basics for this are basically learning about b-trees and then writing specific code to recognize the right tokens (ie "+","-","*","/","(,)") and so on and implement specific functionality to evaluate arguments (like turning strings into integers and so on).

I'm sorry I can't be more specific, but I think it will do you some good to learn about b-trees and if you have any other questions I'll do my best to answer them.

 

[I like Serena]

As long as you only want to evaluate basic expressions you could write a program of about 100 lines to do so.
However, I suspect it would be best to google for a library (or source code) that does this for you.

 

[AlephZero]

If you just want to evaluate numerical expresssions, you don't really need to learn about data structures like B-trees. You can write a recuirsive function (one that calls itself) to take care of that for you.

The geenral idea is: Find the lowest priority operand (+ = * etc) in the string. Split the string into two parts, call your function again to evaluate each part, then do the operation and return the answer.

For example to evaluate (1+2)*3 - 4/5
If you were doing it by hand, the last operation would be the "-".

So if you write a function

int evaluate(string s)

and call

i = evaluate{"(1+2)*3 - 4/5");

the "answer" is returned by doing

 return evaluate{"(1+2)*3") - evaluate("4/5");

(Obviously the real code will use variables to hold the two parts of the string, but I'm showing you the general idea, not writing the routine for you.)

evaluate("(1+2)*3")

is then evaluated the same way, by

return evaluate("(1+2)") * (evaluate("3");

and so on. Handling parentheses are even simpler.

evaluate("(1+2)")

is done by

return evaluate("1+2");

So you need to write the logic that first looks for + and - (but not inside parentheses!), then for * and /, then (), and if there are none of the above just converts the string to an integer. You should be able to do the whole thing in less than 100 lines.

 

[jtbell]

Sorry, I don't know how to process (or parse, as you say) the given equation? Could you help me out with it please?

You need to be aware that parsing and evaluating mathematical expressions is a major topic in compiler design. Most computer science students study it for the first time in a course on algorithms and/or data structures, after they have already become fairly proficient in programming.

I suspect that a Google search for something like "C++ expression evaluator" will turn up code examples and even complete libraries of functions that you can plug into your program.

 

[I like Serena]

So you need to write the logic that first looks for + and - (but not inside parentheses!), then for * and /, then (), and if there are none of the above just converts the string to an integer. You should be able to do the whole thing in less than 100 lines.

On wikipedia the algorithm to parse an infix expression is given in the article:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

It also contains C code for an expression supporting the operators: ! * / % + - =
Note that this program counts 279 lines.


Actually, I've written a C++ module myself once that supports all C++ operators, including the use of variables. It exports the function:

void eval_expression(const std::string& expr, t_value& result, t_value (*get_variable)(const char* name));

and contains 300 lines of code.
If you want I can upload it.

 

[chiro]

AlephZero, you're pretty much doing what a b-tree does without being a b-tree in the strictest sense. Splitting the argument up into two-pieces is what the left and right nodes are!

Obviously you can do this without using the b-tree or graph structures, but sometimes it helps to look at things generically for future problems.

Reason for this is that if you implement general functionality once, you can reuse it to your hearts content and coming up with solutions to new problems is more minimal than if you had to rewrite specific code for every new problem you encountered.

 

[PainterGuy]

Hello everyone,

The best way I think you should go about doing this is to use a binary tree and implement a routine that calculates your expression. I know you probably haven't come across b-trees (ie the binary trees, this is the nickname that they have) so I'll give them in a nutshell.

A binary tree is basically a tree where each node has a left and a right node which is a tree itself. The leaves of the tree are the nodes that don't have any children. So the simplest tree is simply a tree with one node. I'll give a specific example:

Lets say you want to put (9+7)*3 into a tree form. Your root node would have an "*" state and your left child of the root node would be a "+". Your left child of the plus would be a "9" and your right child would be a "3". Going back to to the right child of the "*" node you would have a "3" in your right child.

What happens is that if you evaluate your tree "left to right" you end up calculating your value which is (9+7)*3 = 48. Here is how it works step by step:

Many thanks chiro. With all genuineness it was very helpful in providing me general understanding.

(9+7)*3 -- "*" has nodes on its left and right side therefore it's root node. Don't we consider signs or symbols such as "()" to be nodes? "3" and "9" are leaves.

Wouldn't the right of "+" be "7" instead of "3"?

Help me out with this, please!

As long as you only want to evaluate basic expressions you could write a program of about 100 lines to do so.
However, I suspect it would be best to google for a library (or source code) that does this for you.

Hi I like Serena,

I did not know if it was possible you could get ready-made codes on the google.

This is from your other post in this thread:
Actually, I've written a C++ module myself once that supports all C++ operators, including the use of variables. It exports the function:

void eval_expression(const std::string& expr, t_value& result, t_value (*get_variable)(const char* name));

and contains 300 lines of code.
If you want I can upload it.

My purpose is only to evaluate simple mathematical expressions. Also teach me on how to get your code into the body of my original code (given in my post #1) above. So, I can find ready-made codes on the internet!

If you just want to evaluate numerical expresssions, you don't really need to learn about data structures like B-trees. You can write a recuirsive function (one that calls itself) to take care of that for you.

The geenral idea is: Find the lowest priority operand (+ = * etc) in the string. Split the string into two parts, call your function again to evaluate each part, then do the operation and return the answer.

For example to evaluate (1+2)*3 - 4/5
If you were doing it by hand, the last operation would be the "-".

So if you write a function

int evaluate(string s)

and call

i = evaluate{"(1+2)*3 - 4/5");

the "answer" is returned by doing

 return evaluate{"(1+2)*3") - evaluate("4/5");

(Obviously the real code will use variables to hold the two parts of the string, but I'm showing you the general idea, not writing the routine for you.)

evaluate("(1+2)*3")

is then evaluated the same way, by

return evaluate("(1+2)") * (evaluate("3");

and so on. Handling parentheses are even simpler.

evaluate("(1+2)")

is done by

return evaluate("1+2");

So you need to write the logic that first looks for + and - (but not inside parentheses!), then for * and /, then (), and if there are none of the above just converts the string to an integer. You should be able to do the whole thing in less than 100 lines.

Many thanks AlephZero. You people invest so much energy into helping people like me. So nice. You guys deserve nobel prize of humanity! I will keep on reading the replies in this thread several times until I make sufficient sense out of them for myself.

You need to be aware that parsing and evaluating mathematical expressions is a major topic in compiler design. Most computer science students study it for the first time in a course on algorithms and/or data structures, after they have already become fairly proficient in programming.

I suspect that a Google search for something like "C++ expression evaluator" will turn up code examples and even complete libraries of functions that you can plug into your program.

Thanks jtbell. I can understand your advice. I was just curious to know if it is possible to change a string into an expression.

[I hope my English can be understood a bit easily than before. Well it tool many, many minutes to write. ]

Cheers

 

[I like Serena]

Hi I like Serena,

I did not know if it was possible you could get ready-made codes on the google.

This is from your other post in this thread:
Actually, I've written a C++ module myself once that supports all C++ operators, including the use of variables. It exports the function:

void eval_expression(const std::string& expr, t_value& result, t_value (*get_variable)(const char* name));

and contains 300 lines of code.
If you want I can upload it.

My purpose is only to evaluate simple mathematical expressions. Also teach me on how to get your code into the body of my original code (given in my post #1) above. So, I can find ready-made codes on the internet!

See the attached zip file.
I put your main program in main.cpp and compiled the 2 .cpp files and linked them together and it worked.

Enjoy!

 

[D H]

I know you probably haven't come across b-trees (ie the binary trees, this is the nickname that they have) so I'll give them in a nutshell.

Whoa there! B-trees and binary trees are very different things.

What you wrote about are binary trees: Every non-leaf node has two children. Binary trees are very useful for representing an expression that comprises binary operators such as multiplication, division, addition, and subtraction.

A b-tree is a very different beast. Depending on who you read, the "b" in b-tree stands for "balanced", "Bayer", "Boeing", (and occasionally something else) -- but never "binary".

The below is an example of a b-tree.

A couple of references on b-trees:

http://www.bluerwhite.org/btree/
This article is the source of the above image.

Wikipedia: http://en.wikipedia.org/wiki/B-tree
Right up front, the wiki article forewarns "Not to be confused with Binary tree."

 

[rcgldr]

One common strategy for calculator like programs is to have two primary recursive routines, value(), and expression() which expects to get <value> operator <value> [operator <value> ...]. If value() sees a leading "(", calls expression(). If expression() sees a trailing ")", or end of string, returns the current value it's generated. This doesn't handle precedcence, just parses the string left to right. Unary operators are handled in value(). The initial function called is expression().

 

[PainterGuy]

See the attached zip file.
I put your main program in main.cpp and compiled the 2 .cpp files and linked them together and it worked.

Enjoy!

Many thanks I like Serena. I do appreciate your kind help.

Badly, I am getting a error.

error is:

[Linker error] undefined reference to `eval_expression(std::string const&, int&, int (*)(char const*))'

I am using DevC++ on Windows XP Pro. The zip file contained three files: ExprEval (C++) file, ExprEval (C header file), main (C++) file. There was a Read Me file.

How do I correct this error?

And is ExprEval (C++ Source File) a function file? I mean that is it a code for the function to evaluate strings into math expressions?

Much grateful for all this.

Cheers

 

[I like Serena]

Many thanks I like Serena. I do appreciate your kind help.

Badly, I am getting a error.

error is:

[Linker error] undefined reference to `eval_expression(std::string const&, int&, int (*)(char const*))'

I am using DevC++ on Windows XP Pro. The zip file contained three files: ExprEval (C++) file, ExprEval (C header file), main (C++) file. There was a Read Me file.

How do I correct this error?

And is ExprEval (C++ Source File) a function file? I mean that is it a code for the function to evaluate strings into math expressions?

Much grateful for all this.

Cheers

You need to add the ExprEval.cpp file to your project in DevC++.
That should fix the problem.
The file contains the code for the function mentioned.

 

[PainterGuy]

You need to add the ExprEval.cpp file to your project in DevC++.
That should fix the problem.
The file contains the code for the function mentioned.

Hi I like Serena,

So sorry it is not working. I am newbie to programming and do not know exactly how to create projects in DevC++. But you can check here what I was doing:--
http://img863.imageshack.us/img863/5623/stringexpression.jpg

Now tell me please what to do.

Cheers

 

[I like Serena]

Hi I like Serena,

So sorry it is not working. I am newbie to programming and do not know exactly how to create projects in DevC++. But you can check here what I was doing:--
http://img863.imageshack.us/img863/5623/stringexpression.jpg

Now tell me please what to do.

Cheers

The first error given is that DevC++ cannot find ExprEval.h.
Obviously the file is available in your directory.
So you need to "explain" to DevC++ where it is.
This is done by setting the "Include directory path", which is where DevC++ searches for files that are included with "#include".

I can't recall exactly where that is in DevC++, but I think you need to click "Project" in the menu bar, try to find something like Preprocessor configuration, and then the "Include path". You need to add here the directory where "ExprEval.h" is.

Then try again.

 

[PainterGuy]

The first error given is that DevC++ cannot find ExprEval.h.
Obviously the file is available in your directory.
So you need to "explain" to DevC++ where it is.
This is done by setting the "Include directory path", which is where DevC++ searches for files that are included with "#include".

I can't recall exactly where that is in DevC++, but I think you need to click "Project" in the menu bar, try to find something like Preprocessor configuration, and then the "Include path". You need to add here the directory where "ExprEval.h" is.

Then try again.

Hooray!

It worked! I am so happy!

Many thanks I like Serena. You are so nice.

 

[chiro]

Hello everyone,

Many thanks chiro. With all genuineness it was very helpful in providing me general understanding.

(9+7)*3 -- "*" has nodes on its left and right side therefore it's root node. Don't we consider signs or symbols such as "()" to be nodes? "3" and "9" are leaves.

Wouldn't the right of "+" be "7" instead of "3"?

Help me out with this, please!

With regards to having "(" and ")" as nodes, we don't need to do that. What we do instead is to use this information to create the right tree. If you want to create expressions that use parentheses, you just create the right tree. Basically since you know that the tree is evaluated left to right, leaf to root, you just have to create a tree that simulates the right evaluation.

So basically if you had brackets within brackets, you're expression in the inner most brackets will be deeper in the tree and your outermost brackets will be towards the root node of the tree.

With regards to your question about 9 and 7 with respect to a "+" node, I meant to say that with respect to the "+" node, the 9 is the left child of that "+" node and the 7 is the right child of that "+" node. I think this is what you were asking and if this is was what you were asking, then you are correct.

DH, you are right. For some reason I have always used b-trees to mean some kind of binary tree with a generalized form of a node to represent data at that node. But yeah a binary tree is what I meant to say.

 

[PainterGuy]

With regards to having "(" and ")" as nodes, we don't need to do that. What we do instead is to use this information to create the right tree. If you want to create expressions that use parentheses, you just create the right tree. Basically since you know that the tree is evaluated left to right, leaf to root, you just have to create a tree that simulates the right evaluation.

So basically if you had brackets within brackets, you're expression in the inner most brackets will be deeper in the tree and your outermost brackets will be towards the root node of the tree.

With regards to your question about 9 and 7 with respect to a "+" node, I meant to say that with respect to the "+" node, the 9 is the left child of that "+" node and the 7 is the right child of that "+" node. I think this is what you were asking and if this is was what you were asking, then you are correct.

DH, you are right. For some reason I have always used b-trees to mean some kind of binary tree with a generalized form of a node to represent data at that node. But yeah a binary tree is what I meant to say.

Many, many thanks chiro. Much grateful for this help. Would ask some follow-on questions soon.

Cheers

 

[aphysicsdummy]

Is it easy to extend "I like Serena"'s code to work with expressions that contain hex integers (e.g. "0X004D"), double constants (e.g. "3.1416"), variables (e.g. "d1, d2"), and (e.g. "d[1]", "d[2]")? If there is existing code could someone upload? Thanks!

 

[cheers00]

Hi "I like Serena"', your code doesn't work with decimal numbers. Wondering if it is a easy thing to do.

 

[BMW]

here's a example output:

enter the expression = ((7+7)*9)/9
((7+7)*9)/9
Press any key to continue . . .

Don't you mean this:

enter the expression = ((7+7)*9)/9
14
Press any key to continue . . .

 

[I like Serena]

Hi "I like Serena"', your code doesn't work with decimal numbers. Wondering if it is a easy thing to do.

Yes.
Change the "typedef int t_value" to "typedef double t_value" and decimal numbers will be supported as well.
You will get a couple of errors on bitwise operators, but those can be fixed easily.

 

[cheers00]

Yes.
Change the "typedef int t_value" to "typedef double t_value" and decimal numbers will be supported as well.
You will get a couple of errors on bitwise operators, but those can be fixed easily.

Serena, thanks. But I also had to change isinteger function to isNumber. The following seems to work but let me know if I can make it better.

inline bool isNumber(char *&src, double &number)
{
if (!isdigit(*src))
return false;
int integer = 0;
while (isdigit(*src))
integer = *src++ - '0' + 10 * integer;
number = integer;
if(*src == '.')
{
*src++;
double div = 10;
while (isdigit(*src))
{
number = number + (double)(*src++ - '0') / div;
div = div * 10;
}

}
return true;
}

 

[cheers00]

Yes.
Change the "typedef int t_value" to "typedef double t_value" and decimal numbers will be supported as well.
You will get a couple of errors on bitwise operators, but those can be fixed easily.

Also, can you please give me an example to how to use variable parameter?

cheers

 

[I like Serena]

Serena, thanks. But I also had to change isinteger function to isNumber. The following seems to work but let me know if I can make it better.

inline bool isNumber(char *&src, double &number)
{
if (!isdigit(*src))
return false;
int integer = 0;
while (isdigit(*src))
integer = *src++ - '0' + 10 * integer;
number = integer;
if(*src == '.')
{
*src++;
double div = 10;
while (isdigit(*src))
{
number = number + (double)(*src++ - '0') / div;
div = div * 10;
}

}
return true;
}

You can improve it a bit with:

inline bool isNumber(char *&src, double &number)
{
    int nr_scanned = 0;
    if (sscanf(src, "%g%n", &number, &scanned) == 0)
    {
        return false;
    }
    src += nr_scanned;
    return true;
}

That way you also support alternative representations like ".1e-6".

 

[I like Serena]

Also, can you please give me an example to how to use variable parameter?

cheers

Huh?