CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 22
  1. #1
    Join Date
    Apr 2009
    Posts
    1,355

    [RESOLVED] can i convert a string into a math expression?

    see these string:
    2+3 + 3*(5+5)
    can i convert it to a math expression for calculate?

  2. #2
    Join Date
    Feb 2017
    Posts
    677

    Re: can i convert a string into a math expression?

    Quote Originally Posted by Cambalinho View Post
    see these string:
    2+3 + 3*(5+5)
    can i convert it to a math expression for calculate?
    There is no standard function in C++ that does that (if available in a language it's often called eval).

    The most famous algorithm for this purpose is the Shunting-yard algorithm (by Dijkstra),

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

    I'm sure you can locate a suitable implementation on the net.
    Last edited by wolle; April 2nd, 2018 at 03:31 AM.

  3. #3
    Join Date
    Jun 2003
    Location
    Armenia, Yerevan
    Posts
    720

    Re: can i convert a string into a math expression?

    I have written math expressions' parser and evaluator in C++. It's a C++ wrapper class.
    Works with 1, 2 variable, and thus can handle customized functions from 1,2 arguments for 2d and 3d processing.
    Let me know if you need such functionality in your application and I'll send you the sources.

  4. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: can i convert a string into a math expression?

    Quote Originally Posted by Cambalinho View Post
    see these string:
    2+3 + 3*(5+5)
    can i convert it to a math expression for calculate?
    These types of expressions are called infix and are not really suited for computer evaluation. To make them suitable, they are converted into postfix notation (also called reverse polish notation) which doesn't use brackets, the ordering is strict left to right and the operators come after the operands.

    eg 3 + 4 * 5 infix becomes 3 4 5 * + postfix. (2 + 3) * (4 + 5) becomes 2 3 + 4 5 + * postfix. 2 + 3 + 3 * (5 + 5) infix becomes 2 3 + 3 5 5 + * + postfix. Postfix notation can be easily evaluated using a stack. Numbers are pushed onto the stack and when an operator is found, this is applied to the top 1 or 2 numbers (depending whether it is a unary or binary operator) which are popped from the stack and the result is pushed back to the stack. This is repeated until the end of the postfix expression. The result should be one number on the stack. If this is not true or there is stack underflow then there is an error in the postfix expression. To convert from infix to postfix, there are various methods of which Dijkstra's Shunting-yard is perhaps the most famous (see Wolle's post #2). Another common one is Recursive Descent parser (which is the method I prefer) see https://en.wikipedia.org/wiki/Recursive_descent_parser.

    PS if you use one you're found on the internet, make sure it's fit for your purpose - eg some don't handle unary minus correctly. eg -2 + -3 is a valid infix expression. Some only handle integers etc etc. Do you also need it to handle functions eg sin(), cos(), abs() etc etc.
    Last edited by 2kaud; March 31st, 2018 at 07:40 AM. Reason: PS
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  5. #5
    Join Date
    Apr 2009
    Posts
    1,355

    Re: can i convert a string into a math expression?

    finally i get results:
    Code:
    #include <iostream>#include <string>
    #include <vector>
    #include <sstream>
    
    
    using namespace std;
    
    
    class MathOperators
    {
        public:
    
    
        enum enumMathOperators
        {
            ParenthesesOpen='(',
            ParenthesesClose=')',
            Add='+',
            Minus='-',
            Multiplication ='*',
            Space=' ',
            Division ='/'
        };
    
    
        static bool IsMathOperator(char enMath)
        {
            switch(enMath)
            {
                case ParenthesesOpen:
                case ParenthesesClose:
                case Add:
                case Minus:
                case Multiplication:
                case Space:
                case Division:
                    return true;
                default:
                    return false;
            }
        }
    };
    
    void CalculateExpression(string strMathExpression){
        //clean empty spaces
        for(unsigned int i=0; i<strMathExpression.size(); i++)
        {
            if(strMathExpression[i]== ' ' || strMathExpression[i]== '\t')
            {
                strMathExpression.erase(i,1);
                i=0;
            }
        }
    
    
        //spare the operator and numbers
        //for add them on a vector:
        string strNumber="";
        vector<string> vecOperator;
        int OperatorCount=0;
        
        //we must add a null string terminator
        //for we convert the char to string
        //or we can get unexpected results:
        char chr[]={'0','\0'};
        for(unsigned int i=0; i<=strMathExpression.size() ; i++)
        {
            chr[0]=strMathExpression[i];
            if(isdigit(chr[0]))
            {
                strNumber+=chr[0];
            }
            else
            {
                if(isdigit(strNumber[0]))
                    vecOperator.push_back(strNumber);
                if( MathOperators::IsMathOperator(chr[0])==true)
                {
                    vecOperator.push_back(chr);
                    OperatorCount++;
                }
                OperatorCount++;
                strNumber="";
    
    
            }
        }
    
    
        //print actual vector:
        for (unsigned int a=0; a<vecOperator.size();a++)
        {
            cout << vecOperator[a] << " ";
        }
        cout << "\n";
    
    
        //making the math:
        for(unsigned int i=0;i<vecOperator.size(); i++)
        {
            if(vecOperator[i]=="+")
            {
                //get result in int:
                int result=stoi(vecOperator[i-1])+ stoi(vecOperator[i+1]);
    
    
                //get the result in int to string:
                vecOperator[i-1]= to_string(result);
    
    
                //erase the next 2 elements:
                vecOperator.erase(vecOperator.begin()+i,vecOperator.begin()+i+2);
    
    
                //print the elements after changes:
                for (unsigned int a=0; a<vecOperator.size();a++)
                {
                    cout << vecOperator[a] << " ";
                }
                cout << "\n";
                
                //before continue the i must be -1
                //when the for restart, the i will be 0:
                i=-1;
                continue;
            }
    
    
            else if(vecOperator[i]=="-")
            {
                int result=stoi(vecOperator[i-1])- stoi(vecOperator[i+1]);
                vecOperator[i-1]= to_string(result);
                vecOperator.erase(vecOperator.begin()+i,vecOperator.begin()+i+2);
                for (unsigned int a=0; a<vecOperator.size();a++)
                {
                    cout << vecOperator[a] << " ";
                }
                cout << "\n";
                i=-1;
                continue;
            }
            else if(vecOperator[i]=="/")
            {
                int result=stoi(vecOperator[i-1])/ stoi(vecOperator[i+1]);
                vecOperator[i-1]= to_string(result);
                vecOperator.erase(vecOperator.begin()+i,vecOperator.begin()+i+2);
                for (unsigned int a=0; a<vecOperator.size();a++)
                {
                    cout << vecOperator[a] << " ";
                }
                cout << "\n";
                i=-1;
                continue;
            }
            else if(vecOperator[i]=="*")
            {
                int result=stoi(vecOperator[i-1])* stoi(vecOperator[i+1]);
                vecOperator[i-1]= to_string(result);
                vecOperator.erase(vecOperator.begin()+i,vecOperator.begin()+i+2);
                for (unsigned int a=0; a<vecOperator.size();a++)
                {
                    cout << vecOperator[a] << " ";
                }
                cout << "\n";
                i=-1;
                continue;
            }
        }
    }
    
    
    int main()
    {
        string strExpression;
        getline(cin, strExpression);
        CalculateExpression(strExpression);
        return 0;
    }
    the math is done correctly. can anyone give me 1 advice: how can i control the priory math?
    Name:  Sem TÃ*tulo.jpg
Views: 3616
Size:  16.9 KB
    readers: don't forget see the way that i do the conversion from char array to string... it's very important add the '\0'(string null terminator) for avoid unexpected results

  6. #6
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: can i convert a string into a math expression?

    This code doesn't use mathematical precedence. This evaluates 1 + 2 * 3 as 9 whereas it should be 7 as 1+ 2 * 3 should be evaluated as 1 + (2 * 3). Also it doesn't recognise parenthesis even though they are specified as an operator. There is an error in the 'clean empty space code' which anyhow would usually be done as a single statement

    Code:
    	strMathExpression.erase(remove_if(strMathExpression.begin(), strMathExpression.end(), isspace), strMathExpression.end());
    how can i control the priory math
    You implement an infix to postfix parser as per posts #2 and #4 - which requires a complete re-design of this code so no further comments.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  7. #7
    Join Date
    Apr 2009
    Posts
    1,355

    Re: can i convert a string into a math expression?

    i'm sorry... that line give me several compiler errors, that's why i use the for loop.
    error: "no matching function for call to 'remove_if(std::__cxx11::basic_string<char>::iterator, std::__cxx11::basic_string<char>::iterator, <unresolved overloaded function type>)' "

  8. #8
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: can i convert a string into a math expression?

    Have you got the required #include statements

    Code:
    #include <algorithm>
    #include <cctype>
    #include <string>
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  9. #9
    Join Date
    Apr 2009
    Posts
    1,355

    Re: can i convert a string into a math expression?

    yes. but i'm using code blocks.. maybe that's why i get the errors

  10. #10
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: can i convert a string into a math expression?

    then consider

    Code:
    for(unsigned int i = 0; i < strMathExpression.size();)
            if (strMathExpression[i] == ' ' || strMathExpression[i] == '\t')
                strMathExpression.erase(i,1);
            else
                ++i;
    and also consider upgrading your compiler.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  11. #11
    Join Date
    Apr 2009
    Posts
    1,355

    Re: can i convert a string into a math expression?

    but can you give me an advice for control the operator priority?

  12. #12
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: can i convert a string into a math expression?

    It's beautiful code. Modern C++. Well commented. Tested. Use it and you may even learn something.
    ...but doesn't work with negative numbers (unary minus). -1+2 gives -1946156963 !!

    PS. It also uses integer division. So 3/2*2 gives 2 but 2*3/2 gives 3 whereas mathematically these are the same and should give the same answer (3). Doh!!
    Last edited by 2kaud; April 1st, 2018 at 09:19 AM. Reason: PS
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  13. #13
    Join Date
    Feb 2017
    Posts
    677

    Re: can i convert a string into a math expression?

    Quote Originally Posted by 2kaud View Post
    ...but doesn't work with negative numbers (unary minus). -1+2 gives -1946156963 !!

    PS. It also uses integer division. So 3/2*2 gives 2 but 2*3/2 gives 3 whereas mathematically these are the same and should give the same answer (3). Doh!!
    Sorry, I remove this reference.

  14. #14
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: can i convert a string into a math expression?

    The original link for a shunting-yard c++ implementation was https://gist.github.com/t-mat/b9f681b7591cdae712f6 has issues including those discussed in post #12. There is also a fundamental implementation issue with the shunting for a right parenthesis which has been fixed below. Based upon this code, consider the following code which works with negative numbers and uses floating point rather than integer arithmetic. The main changes are in exprToTokens() which uses the type of the last token as a state indicator to determine whether the current token is valid or not. Also the evaluation code has been placed into eval() so that it is easier to use from within other code. Also eval() now returns a pair which indicates whether the eval() has been successful or not and if it has, the value. No error messages are now displayed. Note that the test code in main() requires c++17 - though it is fairly easy to convert it back to c++14 code.

    Code:
    // Modified from https://gist.github.com/t-mat/b9f681b7591cdae712f6
    
    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <cmath>
    #include <cctype>
    #include <utility>
    
    using Mtype = long double;
    
    struct Token {
    	enum class Type {
    		Unknown = 0,
    		Number,
    		Operator,
    		LeftParen,
    		RightParen,
    	};
    
    	Token(Type t, const std::string& s, int prec = 1, bool ra = false)
    		: type {t}, str(s), precedence {prec}, rightAssociative {ra}
    	{}
    
    	Type type {Type::Unknown};
    	std::string str;
    	int precedence = -1;
    	bool rightAssociative = false;
    };
    
    
    std::deque<Token> exprToTokens(const std::string& expr)
    {
    	const auto isnum = [](char ch) {return isdigit(ch) || (ch == '.');};
    
    	std::deque<Token> tokens;
    	Token::Type lstok = Token::Type::Operator;
    	int nopar = 0;
    
    	for (const auto *p = expr.c_str(); *p;)
    		if (((lstok == Token::Type::Operator) || (lstok == Token::Type::LeftParen)) && (isnum(*p) || (((*p == '-') || (*p == '+')) && isnum(*(p + 1))))) {
    			const char* const b = ((*p == '-') || (*p == '+')) ? p++ : p;
    
    			for (; isnum(*p); ++p);
    			lstok = Token::Type::Number;
    			const auto s = std::string(b, p);
    
    			if (std::count(s.begin(), s.end(), '.') < 2)
    				tokens.push_back(Token {lstok, s});
    			else
    				return {};
    		} else {
    			int pr = -1;		// precedence
    			bool ra = false;	// rightAssociative
    
    			if (((lstok == Token::Type::LeftParen) || (lstok == Token::Type::Operator)) && (*p == '(')) {
    				lstok = Token::Type::LeftParen;
    				++nopar;
    			} else
    				if (((lstok == Token::Type::RightParen) || (lstok == Token::Type::Number)) && (*p == ')')) {
    					lstok = Token::Type::RightParen;
    					--nopar;
    				} else
    					if ((lstok == Token::Type::Number) || (lstok == Token::Type::RightParen)) {
    						lstok = Token::Type::Operator;
    						switch (*p) {
    							case '^':   pr = 4; ra = true;  break;
    							case '*':   pr = 3; break;
    							case '/':   pr = 3; break;
    							case '+':   pr = 2; break;
    							case '-':   pr = 2; break;
    							default:    return {};
    						}
    					} else
    						return {};
    
    			tokens.push_back(Token {lstok, std::string(1, *p), pr, ra});
    			++p;
    		}
    
    	return ((nopar == 0) && ((lstok == Token::Type::RightParen) || (lstok == Token::Type::Number))) ? tokens : std::deque<Token> {};
    }
    
    
    std::deque<Token> shuntingYard(const std::deque<Token>& tokens)
    {
    	std::deque<Token> queue;
    	std::vector<Token> stack;
    
    	// While there are tokens to be read:
    	for (auto token : tokens) {
    		// Read a token
    		switch (token.type) {
    			case Token::Type::Number:
    				// If the token is a number, then add it to the output queue
    				queue.push_back(token);
    				break;
    
    			case Token::Type::Operator:
    			{
    				// If the token is operator, o1, then:
    				const auto o1 = token;
    
    				// while there is an operator token,
    				while (!stack.empty()) {
    					// o2, at the top of stack, and
    					const auto o2 = stack.back();
    
    					// either o1 is left-associative and its precedence is
    					// *less than or equal* to that of o2,
    					// or o1 if right associative, and has precedence
    					// *less than* that of o2,
    					if (!((!o1.rightAssociative && o1.precedence <= o2.precedence) || (o1.rightAssociative && o1.precedence <  o2.precedence)))
    						break;
    
    					// then pop o2 off the stack,
    					stack.pop_back();
    					// onto the output queue;
    					queue.push_back(o2);
    				}
    
    				// push o1 onto the stack.
    				stack.push_back(o1);
    			}
    			break;
    
    			case Token::Type::LeftParen:
    				// If token is left parenthesis, then push it onto the stack
    				stack.push_back(token);
    				break;
    
    			case Token::Type::RightParen:
    				// If token is right parenthesis:
    			{
    				bool match = false;
    				// Until the token at the top of the stack
    				// is a left parenthesis,
    				// pop operators off the stack
    				// onto the output queue.
    				while (!stack.empty() && stack.back().type != Token::Type::LeftParen) {
    					queue.push_back(stack.back());
    					stack.pop_back();
    					match = true;
    				}
    
    				// Pop the left parenthesis from the stack,
    				// but not onto the output queue.
    				stack.pop_back();
    
    				if (!match && stack.empty()) {
    					// If the stack runs out without finding a left parenthesis,
    					// then there are mismatched parentheses.
    					//std::cout << "RightParen error (" << token.str << ")\n";
    					return {};
    				}
    			}
    			break;
    
    			default:
    				//std::cout << "Error (" << token.str << ")\n";
    				return {};
    		}
    	}
    
    	// When there are no more tokens to read:
    	//   While there are still operator tokens in the stack:
    	while (!stack.empty()) {
    		// If the operator token on the top of the stack is a parenthesis,
    		// then there are mismatched parentheses.
    
    		if (stack.back().type == Token::Type::LeftParen) {
    			//std::cout << "Mismatched parentheses error\n";
    			return {};
    		}
    
    		// Pop the operator onto the output queue.
    		queue.push_back(std::move(stack.back()));
    		stack.pop_back();
    	}
    
    	return queue;
    }
    
    std::pair<bool, Mtype> eval(const std::string& expr)
    {
    	const auto tokens = exprToTokens(expr);
    	auto queue = shuntingYard(tokens);
    	std::vector<Mtype> stack;
    
    	while (!queue.empty()) {
    		const auto token = queue.front();
    		queue.pop_front();
    		switch (token.type) {
    			case Token::Type::Number:
    				stack.push_back(std::stold(token.str));
    				break;
    
    			case Token::Type::Operator:
    			{
    				const auto rhs = stack.back();
    				stack.pop_back();
    				const auto lhs = stack.back();
    				stack.pop_back();
    
    				switch (token.str[0]) {
    					default:
    						//std::cout << "Operator error [" << token.str << "]\n";
    						return {false, 0};
    					case '^':
    						stack.push_back(static_cast<Mtype>(pow(lhs, rhs)));
    						break;
    					case '*':
    						stack.push_back(lhs * rhs);
    						break;
    					case '/':
    						stack.push_back(lhs / rhs);
    						break;
    					case '+':
    						stack.push_back(lhs + rhs);
    						break;
    					case '-':
    						stack.push_back(lhs - rhs);
    						break;
    				}
    			}
    			break;
    
    			default:
    				//std::cout << "Token error " << (int)token.type << std::endl;
    				return {false, 0};
    		}
    	}
    
    	return (stack.size() != 1) ? std::make_pair(false, 0.0L) : std::make_pair(true, stack.back());
    }
    
    int main() {
    	//std::string expr = "20-30/3+4*2^3";		// Should give 42
    
    	std::cout << "Enter expression :";
    	std::string expr;
    
    	std::getline(std::cin, expr);
    	expr.erase(std::remove_if(expr.begin(), expr.end(), std::isspace), expr.end());
    
    	if (auto [ok, res] = eval(expr); ok)
    		std::cout << "Result : " << res << std::endl;
    	else
    		std::cout << "Error in expression" << std::endl;
    
    	return 0;
    }
    Examples

    Code:
    Enter expression :-1+-2*-3
    Result : 5
    
    Enter expression :20-30/3+4*2^3
    Result : 42
    
    Enter expression :3/2*2
    Result : 3
    
    Enter expression :(-7+(7^2-4*12)^.5)/2
    Result : -3
    Last edited by 2kaud; April 7th, 2018 at 05:04 AM. Reason: Fixed issue with illegal terminating token
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  15. #15
    Join Date
    Feb 2017
    Posts
    677

    Re: can i convert a string into a math expression?

    Quote Originally Posted by 2kaud View Post
    The original link for a shunting-yard c++ implementation was https://gist.github.com/t-mat/b9f681b7591cdae712f6 has issues including those discussed in post #12.
    Well, I made a mistake to uncritically recommended the GitHub implementation but with your fixes it should be okay now so I recommend your version in #14.

    My advice to the OP really was that if this isn't a exercise it's much better to use an existing implementation. Expression parsing in practice quickly becomes very complicated as soon as you have to deal with more than just the very basic operators,

    http://en.cppreference.com/w/c/langu...tor_precedence
    Last edited by wolle; April 3rd, 2018 at 02:01 AM.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured