-
March 30th, 2018, 12:32 PM
#1
[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?
-
March 30th, 2018, 04:21 PM
#2
Re: can i convert a string into a math expression?
Originally Posted by Cambalinho
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.
-
March 31st, 2018, 04:20 AM
#3
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.
-
March 31st, 2018, 05:08 AM
#4
Re: can i convert a string into a math expression?
Originally Posted by Cambalinho
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)
-
March 31st, 2018, 09:35 AM
#5
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?
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
-
March 31st, 2018, 10:59 AM
#6
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)
-
March 31st, 2018, 11:28 AM
#7
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>)' "
-
March 31st, 2018, 11:37 AM
#8
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)
-
March 31st, 2018, 12:06 PM
#9
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
-
March 31st, 2018, 12:15 PM
#10
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)
-
March 31st, 2018, 12:37 PM
#11
Re: can i convert a string into a math expression?
but can you give me an advice for control the operator priority?
-
April 1st, 2018, 04:55 AM
#12
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)
-
April 2nd, 2018, 03:30 AM
#13
Re: can i convert a string into a math expression?
Originally Posted by 2kaud
...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.
-
April 2nd, 2018, 06:09 AM
#14
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)
-
April 3rd, 2018, 01:11 AM
#15
Re: can i convert a string into a math expression?
Originally Posted by 2kaud
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|