C++

Forum

 
input parser

Geckoo (362)
1
2
3
4
5
 
// 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
seeplus (6457)
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.
Geckoo (362)
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 ++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
#include <string>
#include <iostream>
#include <list>
#include <sstream>

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<std::string>& 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<std::string> 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
seeplus (6457)
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
seeplus (6457)
Consider as somewhat simplified (but no error reporting!):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
#include <string>
#include <iostream>
#include <list>
#include <sstream>
#include <cctype>

std::list<std::string> tokenize(const std::string& str) {
	std::string num;
	std::list<std::string> 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<std::string> 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
seeplus (6457)
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!:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
#include <string>
#include <iostream>
#include <list>
#include <sstream>
#include <cctype>

std::list<std::string> tokenize(const std::string& str) {
	std::string num;
	std::list<std::string> 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 <typename T = int>
class Calculator {
public:
	Calculator(const std::string& expression);

	T exp();

private:
	std::list<std::string> mTokens;
	std::string mCurrent;

	void next();
	T term();
	T factor();
	T toNum(const std::string& s) const;
};

template <typename T>
Calculator<T>::Calculator(const std::string& expression) : mTokens(tokenize(expression)), mCurrent(mTokens.front()) {}

template <typename T>
void Calculator<T>::next() {
	mTokens.pop_front();

	mCurrent = !mTokens.empty() ? mTokens.front() : std::string {};
}

template <typename T>
T Calculator<T>::exp() {
	auto result { term() };

	while (mCurrent == "+" || mCurrent == "-") {
		const auto cur { mCurrent };

		next();
		result += (cur == "+") ? term() : -term();
	}

	return result;
}

template <typename T>
T Calculator<T>::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 <typename T>
T Calculator<T>::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 <typename T>
T Calculator<T>::toNum(const std::string& s) const {
	T x;
	std::stringstream { s } >> x;

	return x;
}

template<typename T = int>
T calculate(const std::string& s) {
	return Calculator<T> { 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<double>(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
Geckoo (362)
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
seeplus (6457)
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.
seeplus (6457)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
 
#include <string>
#include <iostream>
#include <list>
#include <sstream>
#include <type_traits>
#include <iomanip>
#include <cctype>

std::list<std::string> tokenize(const std::string& str) {
	std::string num;
	std::list<std::string> tokens;

	for (size_t i {}; i < str.size(); ++i) {
		const auto c { static_cast<unsigned char>(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 <typename T = int> requires std::is_arithmetic_v<T>
class Calculator {
public:
	Calculator(const std::string& expression);

	T exp();

private:
	std::list<std::string> 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 <typename T> requires std::is_arithmetic_v<T>
Calculator<T>::Calculator(const std::string& expression) : mTokens(tokenize(expression)), mCurrent(mTokens.front()) {}

template <typename T> requires std::is_arithmetic_v<T>
void Calculator<T>::next() {
	mTokens.pop_front();

	mCurrent = !mTokens.empty() ? mTokens.front() : std::string {};
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::exp() {
	return bor();
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::bor() {
	auto result { bxor() };

	if constexpr (std::is_integral_v<T>)
		while (mCurrent == "|") {
			next();
			result |= bxor();
		}

	return result;
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::bxor() {
	auto result { band() };

	if constexpr (std::is_integral_v<T>)
		while (mCurrent == "^") {
			next();
			result ^= band();
		}

	return result;
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::band() {
	auto result { bshift () };

	if constexpr (std::is_integral_v<T>)
		while (mCurrent == "&") {
			next();
			result &= bshift();
		}

	return result;
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::bshift() {
	auto result { plus() };

	if constexpr (std::is_integral_v<T>)
		while (mCurrent == ">>" || mCurrent == "<<") {
			const auto cur { mCurrent };

			next();

			const auto ter { plus() };

			result = (cur == ">>") ? result >> ter : (result << ter);
		}

	return result;
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::plus() {
	auto result { term() };

	while (mCurrent == "+" || mCurrent == "-") {
		const auto cur { mCurrent };

		next();
		result += (cur == "+") ? term() : 0-term();
	}

	return result;
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::term() {
	auto result { factor() };

	while (mCurrent == "*" || mCurrent == "/" || (std::is_integral_v<T> && mCurrent == "%")) {
		if (const auto cur { mCurrent }; next(), cur == "*")
			result *= factor();
		else {
			const auto denominator { factor() };

			if constexpr (std::is_integral_v<T>)
				result = denominator != 0 ? (cur == "/" ? result / denominator : (result % denominator)) : 0;
			else
				result = denominator != 0 ? result / denominator : 0;
		}
	}

	return result;
}

template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::factor() {
	T result {};
	bool neg {};

	if constexpr (std::is_integral_v<T>)
		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 <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::toNum(const std::string& s) const {
	if constexpr (std::is_same_v<T, char> || std::is_same_v<T, signed char > || std::is_same_v<T, unsigned char>) {
		unsigned x;    // for char >> reads as a char - not as a number!
		std::stringstream { s } >> x;

		return static_cast<T>(x);
	}

	T x;
	std::stringstream { s } >> x;

	return x;
}

template<typename T = int> requires std::is_arithmetic_v<T>
T calculate(const std::string& s) {
	return Calculator<T> { 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<unsigned char>(expression1) << '\n';
	std::cout << expression2 << " = " << calculate<double>(expression2) << '\n';
}



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

Last edited on
Geckoo (362)
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
seeplus (6457)
All you now have to do is add error detection & reporting...
seeplus (6457)
For a simplified getNum(), consider:

1
2
3
4
5
6
7
 
template <typename T> requires std::is_arithmetic_v<T>
T Calculator<T>::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++ ....
Topic archived. No new replies allowed.