### input parser ``12345`` ``````// here we can write directly our algorithm so as to generate a track inline char algorithm(int t) { return (~t >> 2) * ((127 & t * (7 & t >> 10)) < (245 & t * (2 + (5 & t >> 14)))); }``````

Hello. I have this function which computes t according to bitwise operations and arithmetic computation. Sometimes this single line of code is really complex. However I am trying to parse a string (an input) in order to get those operands and values. I found some parsers on GitHub so as to do this work, but I would like to do mine. Do you have an (simple) idea in order to parse a string to a lot of operands and integers? Spliting a string is easy, but how could I "translate" vector elements to operands keeping the previous result computation and respecting brackets? Just a first step with one operand like >> so that I can do the others? Thank you for your help ++
Last edited on This expression is in what is called infix notation. To evaluate it needs to be converted into what is called postfix notation. The main 2 methods for doing that are Shunting Yard and Recursive Descent. There's loads of info/code on the internet to do this. eg given an infix expression of 1 + (2 * 3), the postfix expression would be 1 2 3 * +. This takes into account operator precedence and removes all brackets. Evaluating this postfix expression is quite simple using a stack. Thank you @seeplus for the good explanation. I found some good recursive descent codes on the web which allow me to reach what I am trying to do. This code is a first approach and it works well as expected. It uses only simple mathematical operations and brackets, but it is a good example how it should be ++

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173`` ``````#include #include #include #include std::string removeSpaces(const std::string& str) { std::string s(str); int j = 0; int N = s.size(); for (int i = 0; i < N; ++i) { if (s[i] != ' ') { s[j] = s[i]; j++; } } s.resize(j); return s; } void tokenize(const std::string& str, std::list& tokens) { std::string num; int N = str.size(); for (int i = 0; i < N; ++i) { char c = str[i]; if (isdigit(c)) num += c; else { if (!num.empty()) { tokens.push_back(num); num.clear(); } std::string token; token += c; tokens.push_back(token); } } if (!num.empty()) { tokens.push_back(num); num.clear(); } } class Calculator { public: Calculator(const std::string& expression); void next(); int exp(); int term(); int factor(); int toInt(const std::string& s); private: std::list mTokens; std::string mCurrent; }; Calculator::Calculator(const std::string& expression) { std::string s = removeSpaces(expression); tokenize(s, mTokens); mCurrent = mTokens.front(); } void Calculator::next() { mTokens.pop_front(); if (!mTokens.empty()) mCurrent = mTokens.front(); else mCurrent = std::string(); } int Calculator::exp() { int result = term(); while (mCurrent == "+" || mCurrent == "-") { if (mCurrent == "+") { next(); result += term(); } if (mCurrent == "-") { next(); result -= term(); } } return result; } int Calculator::term() { int result = factor(); while (mCurrent == "*" || mCurrent == "/") { if (mCurrent == "*") { next(); result *= factor(); } if (mCurrent == "/") { next(); int denominator = factor(); if (denominator != 0) result /= denominator; else result = 0; } } return result; } int Calculator::factor() { int result; if (mCurrent == "(") { next(); result = exp(); next(); } else { result = toInt(mCurrent); next(); } return result; } int Calculator::toInt(const std::string& s) { std::stringstream ss; ss << s; int x; ss >> x; return x; } int calculate(std::string s) { Calculator *calculator = new Calculator(s); return calculator->exp(); delete calculator; } int main() { std::string expression = "(7*(2+3)-5)/2"; std::cout << expression << " = " << calculate(expression) << std::endl; return 0; }``````
Last edited on Note L164. This will never be executed due to the return statement on L162!

Also, why use dynamic memory here?

You don't need removeSpaces() as white-space can be handled easily with tokenize(). Also it would the code slightly easier if tokenize() returned tokens rather than having it as a param.

For calculate(), shouldn't s be passed by const ref and not by value?

 It uses only simple mathematical operations and brackets

Yes - but with no expression error reporting. In practice any invalid expression would be reported. Also, it doesn't deal with unary + or -.
Last edited on Consider as somewhat simplified (but no error reporting!):

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117`` ``````#include #include #include #include #include std::list tokenize(const std::string& str) { std::string num; std::list tokens; for (unsigned char c : str) { if (std::isspace(c)) continue; if (std::isdigit(c)) num += c; else { if (!num.empty()) { tokens.push_back(num); num.clear(); } tokens.emplace_back(1, c); } } if (!num.empty()) { tokens.push_back(num); num.clear(); } return tokens; } class Calculator { public: Calculator(const std::string& expression); int exp(); private: std::list mTokens; std::string mCurrent; void next(); int term(); int factor(); int toInt(const std::string& s) const; }; Calculator::Calculator(const std::string& expression) : mTokens(tokenize(expression)), mCurrent(mTokens.front()) {} void Calculator::next() { mTokens.pop_front(); mCurrent = !mTokens.empty() ? mTokens.front() : std::string {}; } int Calculator::exp() { auto result { term() }; while (mCurrent == "+" || mCurrent == "-") { const auto cur { mCurrent }; next(); result += (cur == "+") ? term() : -term(); } return result; } int Calculator::term() { auto result { factor() }; while (mCurrent == "*" || mCurrent == "/") { if (const auto cur { mCurrent }; next(), cur == "*") result *= factor(); else { const auto denominator { factor() }; result = denominator != 0 ? result / denominator : 0; } } return result; } int Calculator::factor() { int result {}; if (mCurrent == "(") { next(); result = exp(); } else result = toInt(mCurrent); next(); return result; } int Calculator::toInt(const std::string& s) const { int x; std::stringstream { s } >> x; return x; } int calculate(const std::string& s) { return Calculator { s }.exp(); } int main() { const std::string expression { "(7 * (2 + 3) - 5) / 2" }; std::cout << expression << " = " << calculate(expression) << '\n'; }``````

 ``` (7 * (2 + 3) - 5) / 2 = 15 ```

Last edited on factor() changed to allow unary + and -. Also to deal with decimal numbers (but not scientific notation) and to enable type of result to be specified. Again, without any error reporting!:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132`` ``````#include #include #include #include #include std::list tokenize(const std::string& str) { std::string num; std::list tokens; for (unsigned char c : str) { if (std::isspace(c)) continue; if (std::isdigit(c) || c == '.') num += c; else { if (!num.empty()) { tokens.push_back(num); num.clear(); } tokens.emplace_back(1, c); } } if (!num.empty()) { tokens.push_back(num); num.clear(); } return tokens; } template class Calculator { public: Calculator(const std::string& expression); T exp(); private: std::list mTokens; std::string mCurrent; void next(); T term(); T factor(); T toNum(const std::string& s) const; }; template Calculator::Calculator(const std::string& expression) : mTokens(tokenize(expression)), mCurrent(mTokens.front()) {} template void Calculator::next() { mTokens.pop_front(); mCurrent = !mTokens.empty() ? mTokens.front() : std::string {}; } template T Calculator::exp() { auto result { term() }; while (mCurrent == "+" || mCurrent == "-") { const auto cur { mCurrent }; next(); result += (cur == "+") ? term() : -term(); } return result; } template T Calculator::term() { auto result { factor() }; while (mCurrent == "*" || mCurrent == "/") { if (const auto cur { mCurrent }; next(), cur == "*") result *= factor(); else { const auto denominator { factor() }; result = denominator != 0 ? result / denominator : 0; } } return result; } template T Calculator::factor() { T result {}; bool neg {}; if (mCurrent == "+" || mCurrent == "-") { neg = mCurrent == "-"; next(); } if (mCurrent == "(") { next(); result = exp(); } else result = toNum(mCurrent); next(); return neg ? -result : result; } template T Calculator::toNum(const std::string& s) const { T x; std::stringstream { s } >> x; return x; } template T calculate(const std::string& s) { return Calculator { s }.exp(); } int main() { const std::string expression1 { "(7 * (2 + 3) - 5) / 2" }; const std::string expression2 { "-(-5.1--6.4)" }; std::cout << expression1 << " = " << calculate(expression1) << '\n'; std::cout << expression2 << " = " << calculate(expression2) << '\n'; }``````

What other operators do you want to add? bit &, | are fairly easy and so is ^ (for power instead of x-or in c/c++). Adding a 2-char operator (eg <<, >> for bit shift) is a bit more tricky...
Last edited on Really good script - especially the last one. This evening I was working on this script including some features, but yours is better and more readable than mine. To answer to your question, I want to include in this equation all bitwise operands like >> << & ~ ^ % and |. Also I would like to implement a ternary operator (so I will add after bitwise operands ? and : - maybe a little bit more complex). It becomes interesting after some hours...
Thank you for your help ++
Last edited on In which case you need to recode tokenize() so that it can recognize operands of more than one char. First though, I would recommend adding error detection/reporting to the current code. As I said before, adding new single char operands is fairly easy once you know the operator precedence required. For each different precedence you simply add a new function and have the function calls changed as appropriate. This implements the bit operators (>>, <<, &, |, ^, ~). As Calculator can now operate on any valid arithmetic type, then special tests have to be made for these (and also %) which only operate on integral types. It also uses C++20 concepts to ensure Calculator only uses an arithmetic type.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230`` ``````#include #include #include #include #include #include #include std::list tokenize(const std::string& str) { std::string num; std::list tokens; for (size_t i {}; i < str.size(); ++i) { const auto c { static_cast(str[i]) }; if (std::isspace(c)) continue; if (std::isdigit(c) || c == '.') num += c; else { if (!num.empty()) { tokens.push_back(num); num.clear(); } size_t rep { 1 }; if (str.size() > 1 && i < str.size() - 1) if ((c == '>' && str[i + 1] == '>') || (c == '<' && str[i + 1] == '<')) { ++i; ++rep; } tokens.emplace_back(rep, c); } } if (!num.empty()) { tokens.push_back(num); num.clear(); } return tokens; } template requires std::is_arithmetic_v class Calculator { public: Calculator(const std::string& expression); T exp(); private: std::list mTokens; std::string mCurrent; void next(); T bshift(); T band(); T bxor(); T bor(); T plus(); T term(); T factor(); T toNum(const std::string& s) const; }; template requires std::is_arithmetic_v Calculator::Calculator(const std::string& expression) : mTokens(tokenize(expression)), mCurrent(mTokens.front()) {} template requires std::is_arithmetic_v void Calculator::next() { mTokens.pop_front(); mCurrent = !mTokens.empty() ? mTokens.front() : std::string {}; } template requires std::is_arithmetic_v T Calculator::exp() { return bor(); } template requires std::is_arithmetic_v T Calculator::bor() { auto result { bxor() }; if constexpr (std::is_integral_v) while (mCurrent == "|") { next(); result |= bxor(); } return result; } template requires std::is_arithmetic_v T Calculator::bxor() { auto result { band() }; if constexpr (std::is_integral_v) while (mCurrent == "^") { next(); result ^= band(); } return result; } template requires std::is_arithmetic_v T Calculator::band() { auto result { bshift () }; if constexpr (std::is_integral_v) while (mCurrent == "&") { next(); result &= bshift(); } return result; } template requires std::is_arithmetic_v T Calculator::bshift() { auto result { plus() }; if constexpr (std::is_integral_v) while (mCurrent == ">>" || mCurrent == "<<") { const auto cur { mCurrent }; next(); const auto ter { plus() }; result = (cur == ">>") ? result >> ter : (result << ter); } return result; } template requires std::is_arithmetic_v T Calculator::plus() { auto result { term() }; while (mCurrent == "+" || mCurrent == "-") { const auto cur { mCurrent }; next(); result += (cur == "+") ? term() : 0-term(); } return result; } template requires std::is_arithmetic_v T Calculator::term() { auto result { factor() }; while (mCurrent == "*" || mCurrent == "/" || (std::is_integral_v && mCurrent == "%")) { if (const auto cur { mCurrent }; next(), cur == "*") result *= factor(); else { const auto denominator { factor() }; if constexpr (std::is_integral_v) result = denominator != 0 ? (cur == "/" ? result / denominator : (result % denominator)) : 0; else result = denominator != 0 ? result / denominator : 0; } } return result; } template requires std::is_arithmetic_v T Calculator::factor() { T result {}; bool neg {}; if constexpr (std::is_integral_v) if (mCurrent == "~") { next(); result = toNum(mCurrent); next(); return ~result; } if (mCurrent == "+" || mCurrent == "-") { neg = mCurrent == "-"; next(); } if (mCurrent == "(") { next(); result = exp(); } else result = toNum(mCurrent); next(); return neg ? 0-result : result; } template requires std::is_arithmetic_v T Calculator::toNum(const std::string& s) const { if constexpr (std::is_same_v || std::is_same_v || std::is_same_v) { unsigned x; // for char >> reads as a char - not as a number! std::stringstream { s } >> x; return static_cast(x); } T x; std::stringstream { s } >> x; return x; } template requires std::is_arithmetic_v T calculate(const std::string& s) { return Calculator { s }.exp(); } int main() { //const std::string expression1 { "(7 * (2 + 3) - 5) / 2" }; const std::string expression1 { "2 + ~240 - 3" }; const std::string expression2 { "-(-5.1--6.4)" }; std::cout << expression1 << " = " << (unsigned)calculate(expression1) << '\n'; std::cout << expression2 << " = " << calculate(expression2) << '\n'; }``````

 ``` 2 + ~240 - 3 = 14 -(-5.1--6.4) = -1.3 ```

Last edited on Hello @seeplus - I am very impressed how you can quickly code a full script when I have to work on it during a few hours. I reached something more or less similar than yours, but I was not really satisfied by mine. Thank you very much for your kind help. There are many interesting things inside your script - a great C++ lesson for me ++
Last edited on All you now have to do is add error detection & reporting... For a simplified getNum(), consider:

 ``1234567`` ``````template requires std::is_arithmetic_v T Calculator::toNum(const std::string& s) const { T x {}; std::from_chars(s.data(), s.data() + s.size(), x); return x; }``````

Note that it now also requires #include <charconv>

 quickly code a full script

I wrote my first parser in Dartmouth Basic over 50 years ago. Since I've coded variations of them in Fortran, Pascal, Algol68, various Assemblers and other basics, c and C++ ....
Registered users can post here. Sign in or register to post.