CoCalc -- expression

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

GitHub Repository: hrydgard/ppsspp
Path: blob/master/Common/Math/expression_parser.cpp
Views: ¹⁴⁰¹
1
#include "Common/StringUtils.h"
2
#include "expression_parser.h"
3
#include <ctype.h>
4
#include <cstring>
5
#include <cstdio>
6
#include <cstdlib>
7

8
typedef enum {
9
	EXOP_BRACKETL, EXOP_BRACKETR, EXOP_MEML, EXOP_MEMR, EXOP_MEMSIZE, EXOP_SIGNPLUS, EXOP_SIGNMINUS,
10
	EXOP_BITNOT, EXOP_LOGNOT, EXOP_MUL, EXOP_DIV, EXOP_MOD, EXOP_ADD, EXOP_SUB,
11
	EXOP_SHL, EXOP_SHR, EXOP_GREATEREQUAL, EXOP_GREATER, EXOP_LOWEREQUAL, EXOP_LOWER,
12
	EXOP_EQUAL, EXOP_NOTEQUAL, EXOP_BITAND, EXOP_XOR, EXOP_BITOR, EXOP_LOGAND,
13
	EXOP_LOGOR, EXOP_TERTIF, EXOP_TERTELSE, EXOP_NUMBER, EXOP_MEM, EXOP_NONE, EXOP_COUNT
14
} ExpressionOpcodeType;
15

16
typedef enum { EXCOMM_CONST, EXCOMM_CONST_FLOAT, EXCOMM_REF, EXCOMM_OP } ExpressionCommand;
17

18
static std::string expressionError;
19

20
typedef struct {
21
	char Name[4];
22
	unsigned char Priority;
23
	unsigned char len;
24
	unsigned char args;
25
	bool sign;
26
} ExpressionOpcode;
27

28
const ExpressionOpcode ExpressionOpcodes[] = {
29
	{ "(",	25,	1,	0,	false },	// EXOP_BRACKETL
30
	{ ")",	25,	1,	0,	false },	// EXOP_BRACKETR
31
	{ "[",	4,	1,	0,	false },	// EXOP_MEML
32
	{ "]",	4,	1,	0,	false },	// EXOP_MEMR
33
	{ ",",	5,	1,	2,	false },	// EXOP_MEMSIZE
34
	{ "+",	22,	1,	1,	true  },	// EXOP_SIGNPLUS
35
	{ "-",	22,	1,	1,	true  },	// EXOP_SIGNMINUS
36
	{ "~",	22,	1,	1,	false },	// EXOP_BITNOT
37
	{ "!",	22,	1,	1,	false },	// EXOP_LOGNOT
38
	{ "*",	21,	1,	2,	false },	// EXOP_MUL
39
	{ "/",	21,	1,	2,	false },	// EXOP_DIV
40
	{ "%",	21,	1,	2,	false },	// EXOP_MOD
41
	{ "+",	20,	1,	2,	false },	// EXOP_ADD
42
	{ "-",	20,	1,	2,	false },	// EXOP_SUB
43
	{ "<<",	19,	2,	2,	false },	// EXOP_SHL
44
	{ ">>",	19,	2,	2,	false },	// EXOP_SHR
45
	{ ">=",	18,	2,	2,	false },	// EXOP_GREATEREQUAL
46
	{ ">",	18,	1,	2,	false },	// EXOP_GREATER
47
	{ "<=",	18,	2,	2,	false },	// EXOP_LOWEREQUAL
48
	{ "<",	18,	1,	2,	false },	// EXOP_LOWER
49
	{ "==",	17,	2,	2,	false },	// EXOP_EQUAL
50
	{ "!=",	17,	2,	2,	false },	// EXOP_NOTEQUAL
51
	{ "&",	16,	1,	2,	false },	// EXOP_BITAND
52
	{ "^",	15,	1,	2,	false },	// EXOP_XOR
53
	{ "|",	14,	1,	2,	false },	// EXOP_BITOR
54
	{ "&&",	13,	2,	2,	false },	// EXOP_LOGAND
55
	{ "||",	12,	2,	2,	false },	// EXOP_LOGOR
56
	{ "?",	10,	1,	0,	false },	// EXOP_TERTIF
57
	{ ":",	11,	1,	3,	false },	// EXOP_TERTELSE
58
	{ "",	0,	0,	0,	false },	// EXOP_NUMBER
59
	{ "[]",	0,	0,	1,	false },	// EXOP_MEM
60
	{ "",	0,	0,	0,	false }		// EXOP_NONE
61
};
62

63
static int radixFromZeroPrefix(char c) {
64
	switch (tolower(c)) {
65
	case 'b': return 2;
66
	case 'o': return 8;
67
	case 'x': return 16;
68
	// Inventing a prefix since we default to hex.
69
	case 'd': return 10;
70
	}
71

72
	return -1;
73
}
74

75
static int radixFromSuffix(char c, int defaultrad) {
76
	switch (tolower(c)) {
77
	case 'o': return 8;
78
	case 'h': return 16;
79
	case 'i': return 10;
80
	case 'u': return 10;
81
	case 'b': return defaultrad == 16 ? -1 : 2;
82
	}
83

84
	return -1;
85
}
86

87
bool parseNumber(char *str, int defaultrad, int len, uint32_t &result) {
88
	int val = 0;
89
	int r = 0;
90
	if (len == 0)
91
		len = (int)strlen(str);
92

93
	if (str[0] == '0' && radixFromZeroPrefix(str[1]) != -1) {
94
		r = radixFromZeroPrefix(str[1]);
95
		str += 2;
96
		len -= 2;
97
	} else if (str[0] == '$') {
98
		r = 16;
99
		str++;
100
		len--;
101
	} else if (str[0] >= '0' && str[0] <= '9') {
102
		int suffix = radixFromSuffix(str[len - 1], defaultrad);
103
		if (suffix != -1) {
104
			r = suffix;
105
			len--;
106
		} else {
107
			r = defaultrad;
108
		}
109
	} else {
110
		return false;
111
	}
112

113
	switch (r)
114
	{
115
	case 2: // bin
116
		while (len--)
117
		{
118
			if (*str != '0' && *str != '1') return false;
119
			val = val << 1;
120
			if (*str++ == '1')
121
			{
122
				val++;
123
			}
124
		}
125
		break;
126
	case 8: // oct
127
		while (len--)
128
		{
129
			if (*str < '0' || *str > '7') return false;
130
			val = val << 3;
131
			val+=(*str++-'0');
132
		}
133
		break;
134
	case 10: // dec
135
		while (len--)
136
		{
137
			if (*str < '0' || *str > '9') return false;
138
			val = val * 10;
139
			val += (*str++ - '0');
140
		}
141
		break;
142
	case 16: // hex
143
		while (len--)
144
		{
145
			char c = tolower(*str++);
146
			if ((c < '0' || c > '9') && (c < 'a' || c > 'f')) return false;
147
			val = val << 4;
148

149
			if (c >= 'a') val += c-'a'+10;
150
			else val += c-'0';
151
		}
152
		break;
153
	default:
154
		return false;
155
	}
156

157
	result = val;
158
	return true;
159
}
160

161
// Parse only a float, and return as float bits.
162
static bool parseFloat(const char *str, int len, uint32_t &result)
163
{
164
	bool foundDecimal = false;
165
	for (int i = 0; i < len; ++i)
166
	{
167
		if (str[i] == '.')
168
		{
169
			if (foundDecimal)
170
				return false;
171
			foundDecimal = true;
172
			continue;
173
		}
174
		if (str[i] < '0' || str[i] > '9')
175
			return false;
176
	}
177

178
	float f = (float)atof(str);
179
	memcpy(&result, &f, sizeof(result));
180
	return foundDecimal;
181
}
182

183
ExpressionOpcodeType getExpressionOpcode(const char* str, int& ReturnLen, ExpressionOpcodeType LastOpcode)
184
{
185
	int longestlen = 0;
186
	ExpressionOpcodeType result = EXOP_NONE;
187

188
	for (int i = 0; i < EXOP_NUMBER; i++)
189
	{
190
		if (ExpressionOpcodes[i].sign == true &&
191
			(LastOpcode == EXOP_NUMBER || LastOpcode == EXOP_BRACKETR)) continue;
192

193
		int len = ExpressionOpcodes[i].len;
194
		if (len > longestlen)
195
		{
196
			if (strncmp(ExpressionOpcodes[i].Name,str,len) == 0)
197
			{
198
				result = (ExpressionOpcodeType) i;
199
				longestlen = len;
200
			}
201
		}
202
	}
203

204
	ReturnLen = longestlen;
205
	return result;
206
}
207

208
bool isAlphaNum(char c)
209
{
210
	if ((c >= '0' && c <= '9') ||
211
		(c >= 'A' && c <= 'Z') ||
212
		(c >= 'a' && c <= 'z') ||
213
		c == '@' || c == '_' || c == '$' || c == '.')
214
	{
215
		return true;
216
	} else {
217
		return false;
218
	}
219
}
220

221
bool initPostfixExpression(const char* infix, IExpressionFunctions* funcs, PostfixExpression& dest)
222
{
223
	expressionError.clear();
224

225
	int infixPos = 0;
226
	int infixLen = (int)strlen(infix);
227
	ExpressionOpcodeType lastOpcode = EXOP_NONE;
228
	std::vector<ExpressionOpcodeType> opcodeStack;
229
	dest.clear();
230

231
	while (infixPos < infixLen)
232
	{
233
		char first = tolower(infix[infixPos]);
234
		char subStr[256];
235
		int subPos = 0;
236

237
		if (first == ' ' || first == '\t')
238
		{
239
			infixPos++;
240
			continue;
241
		}
242

243
		if (first >= '0' && first <= '9')
244
		{
245
			while (isAlphaNum(infix[infixPos]))
246
			{
247
				subStr[subPos++] = infix[infixPos++];
248
			}
249
			subStr[subPos] = 0;
250

251
			uint32_t value;
252
			bool isFloat = false;
253
			if (parseFloat(subStr,subPos,value) == true)
254
				isFloat = true;
255
			else if (parseNumber(subStr,16,subPos,value) == false)
256
			{
257
				expressionError = StringFromFormat("Invalid number \"%s\"", subStr);
258
				return false;
259
			}
260

261
			dest.emplace_back(isFloat?EXCOMM_CONST_FLOAT:EXCOMM_CONST,value);
262
			lastOpcode = EXOP_NUMBER;
263
		} else if ((first >= 'a' && first <= 'z') || first == '@')
264
		{
265
			while (isAlphaNum(infix[infixPos]))
266
			{
267
				subStr[subPos++] = infix[infixPos++];
268
			}
269
			subStr[subPos] = 0;
270

271
			uint32_t value;
272
			if (funcs->parseReference(subStr,value) == true)
273
			{
274
				dest.emplace_back(EXCOMM_REF,value);
275
				lastOpcode = EXOP_NUMBER;
276
				continue;
277
			}
278

279
			if (funcs->parseSymbol(subStr,value) == true)
280
			{
281
				dest.emplace_back(EXCOMM_CONST,value);
282
				lastOpcode = EXOP_NUMBER;
283
				continue;
284
			}
285

286
			expressionError = StringFromFormat("Invalid symbol \"%s\"", subStr);
287
			return false;
288
		} else {
289
			int len;
290
			ExpressionOpcodeType type = getExpressionOpcode(&infix[infixPos],len,lastOpcode);
291
			if (type == EXOP_NONE)
292
			{
293
				expressionError = StringFromFormat("Invalid operator at \"%s\"", &infix[infixPos]);
294
				return false;
295
			}
296

297
			switch (type)
298
			{
299
			case EXOP_BRACKETL:
300
			case EXOP_MEML:
301
				opcodeStack.push_back(type);
302
				break;
303
			case EXOP_BRACKETR:
304
				while (true)
305
				{
306
					if (opcodeStack.empty())
307
					{		
308
						expressionError = "Closing parenthesis without opening one";
309
						return false;
310
					}
311
					ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
312
					opcodeStack.pop_back();
313
					if (t == EXOP_BRACKETL) break;
314
					dest.emplace_back(EXCOMM_OP,t);
315
				}
316
				break;
317
			case EXOP_MEMR:
318
				while (true)
319
				{
320
					if (opcodeStack.empty())
321
					{		
322
						expressionError = "Closing bracket without opening one";
323
						return false;
324
					}
325
					ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
326
					opcodeStack.pop_back();
327
					if (t == EXOP_MEML)
328
					{
329
						dest.emplace_back(EXCOMM_OP,EXOP_MEM);
330
						break;
331
					}
332
					dest.emplace_back(EXCOMM_OP,t);
333
				}
334
				type = EXOP_NUMBER;
335
				break;
336
			default:
337
				if (opcodeStack.empty() == false)
338
				{
339
					int CurrentPriority = ExpressionOpcodes[type].Priority;
340
					while (!opcodeStack.empty())
341
					{
342
						ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
343
						opcodeStack.pop_back();
344

345
						if (t == EXOP_BRACKETL || t == EXOP_MEML)
346
						{
347
							opcodeStack.push_back(t);
348
							break;
349
						}
350

351
						if (ExpressionOpcodes[t].Priority >= CurrentPriority)
352
						{
353
							dest.emplace_back(EXCOMM_OP,t);
354
						} else {
355
							opcodeStack.push_back(t);
356
							break;
357
						}
358
					}
359
				}
360
				opcodeStack.push_back(type);
361
				break;
362
			}
363
			infixPos += len;
364
			lastOpcode = type;
365
		}
366
	}
367

368
	while (!opcodeStack.empty())
369
	{
370
		ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
371
		opcodeStack.pop_back();
372

373
		if (t == EXOP_BRACKETL)	// opening bracket without closing one
374
		{
375
			expressionError = "Parenthesis not closed";
376
			return false;
377
		}
378
		dest.emplace_back(EXCOMM_OP,t);
379
	}
380

381
#if 0			// only for testing
382
	char test[1024];
383
	int testPos = 0;
384
	for (int i = 0; i < dest.size(); i++)
385
	{
386
		switch (dest[i].first)
387
		{
388
		case EXCOMM_CONST:
389
		case EXCOMM_CONST_FLOAT:
390
			testPos += snprintf(&test[testPos], sizeof(test) - testPos, "0x%04X ", dest[i].second);
391
			break;
392
		case EXCOMM_REF:
393
			testPos += snprintf(&test[testPos], sizeof(test) - testPos, "r%d ", dest[i].second);
394
			break;
395
		case EXCOMM_OP:
396
			testPos += snprintf(&test[testPos], sizeof(test) - testPos, "%s ", ExpressionOpcodes[dest[i].second].Name);
397
			break;
398
		};
399
	}
400
#endif
401

402
	return true;
403
}
404

405
bool parsePostfixExpression(PostfixExpression& exp, IExpressionFunctions* funcs, uint32_t& dest)
406
{
407
	size_t num = 0;
408
	uint32_t opcode;
409
	std::vector<uint32_t> valueStack;
410
	unsigned int arg[5]{};
411
	float fArg[5]{};
412
	bool useFloat = false;
413

414
	while (num < exp.size())
415
	{
416
		switch (exp[num].first)
417
		{
418
		case EXCOMM_CONST:	// konstante zahl
419
			valueStack.push_back(exp[num++].second);
420
			break;
421
		case EXCOMM_CONST_FLOAT:
422
			useFloat = true;
423
			valueStack.push_back(exp[num++].second);
424
			break;
425
		case EXCOMM_REF:
426
			useFloat = useFloat || funcs->getReferenceType(exp[num].second) == EXPR_TYPE_FLOAT;
427
			opcode = funcs->getReferenceValue(exp[num++].second);
428
			valueStack.push_back(opcode);
429
			break;
430
		case EXCOMM_OP:	// opcode
431
			opcode = exp[num++].second;
432
			if (valueStack.size() < ExpressionOpcodes[opcode].args)
433
			{
434
				expressionError = "Not enough arguments";
435
				return false;
436
			}
437
			for (int l = 0; l < ExpressionOpcodes[opcode].args; l++)
438
			{
439
				arg[l] = valueStack[valueStack.size()-1];
440
				valueStack.pop_back();
441
			}
442
			// In case of float representation.
443
			memcpy(fArg, arg, sizeof(fArg));
444

445
			switch (opcode)
446
			{
447
			case EXOP_MEMSIZE:	// must be followed by EXOP_MEM
448
				if (exp[num++].second != EXOP_MEM)
449
				{
450
					expressionError = "Invalid memsize operator";
451
					return false;
452
				}
453

454
				uint32_t val;
455
				if (funcs->getMemoryValue(arg[1], arg[0], val, &expressionError) == false)
456
				{
457
					return false;
458
				}
459
				valueStack.push_back(val);
460
				break;
461
			case EXOP_MEM:
462
				{
463
					uint32_t val;
464
					if (funcs->getMemoryValue(arg[0], 4, val, &expressionError) == false)
465
					{
466
						return false;
467
					}
468
					valueStack.push_back(val);
469
				}
470
				break;
471
			case EXOP_SIGNPLUS:		// keine aktion nötig
472
				break;
473
			case EXOP_SIGNMINUS:	// -0
474
				if (useFloat)
475
					valueStack.push_back((uint32_t)(0.0f - fArg[0]));
476
				else
477
					valueStack.push_back(0-arg[0]);
478
				break;
479
			case EXOP_BITNOT:			// ~b
480
				valueStack.push_back(~arg[0]);
481
				break;
482
			case EXOP_LOGNOT:			// !b
483
				valueStack.push_back(!(arg[0] != 0));
484
				break;
485
			case EXOP_MUL:			// a*b
486
				if (useFloat)
487
					valueStack.push_back((uint32_t)(fArg[1] * fArg[0]));
488
				else
489
					valueStack.push_back(arg[1]*arg[0]);
490
				break;
491
			case EXOP_DIV:			// a/b
492
				if (arg[0] == 0)
493
				{
494
					expressionError = "Division by zero";
495
					return false;
496
				}
497
				if (useFloat)
498
					valueStack.push_back((uint32_t)(fArg[1] / fArg[0]));
499
				else
500
					valueStack.push_back(arg[1]/arg[0]);
501
				break;
502
			case EXOP_MOD:			// a%b
503
				if (arg[0] == 0)
504
				{
505
					expressionError = "Modulo by zero";
506
					return false;
507
				}
508
				valueStack.push_back(arg[1]%arg[0]);
509
				break;
510
			case EXOP_ADD:			// a+b
511
				if (useFloat)
512
					valueStack.push_back((uint32_t)(fArg[1] + fArg[0]));
513
				else
514
					valueStack.push_back(arg[1]+arg[0]);
515
				break;
516
			case EXOP_SUB:			// a-b
517
				if (useFloat)
518
					valueStack.push_back((uint32_t)(fArg[1] - fArg[0]));
519
				else
520
					valueStack.push_back(arg[1]-arg[0]);
521
				break;
522
			case EXOP_SHL:			// a<<b
523
				valueStack.push_back(arg[1]<<arg[0]);
524
				break;
525
			case EXOP_SHR:			// a>>b
526
				valueStack.push_back(arg[1]>>arg[0]);
527
				break;
528
			case EXOP_GREATEREQUAL:		// a >= b
529
				if (useFloat)
530
					valueStack.push_back(fArg[1]>=fArg[0]);
531
				else
532
					valueStack.push_back(arg[1]>=arg[0]);
533
				break;
534
			case EXOP_GREATER:			// a > b
535
				if (useFloat)
536
					valueStack.push_back(fArg[1]>fArg[0]);
537
				else
538
					valueStack.push_back(arg[1]>arg[0]);
539
				break;
540
			case EXOP_LOWEREQUAL:		// a <= b
541
				if (useFloat)
542
					valueStack.push_back(fArg[1]<=fArg[0]);
543
				else
544
					valueStack.push_back(arg[1]<=arg[0]);
545
				break;
546
			case EXOP_LOWER:			// a < b
547
				if (useFloat)
548
					valueStack.push_back(fArg[1]<fArg[0]);
549
				else
550
					valueStack.push_back(arg[1]<arg[0]);
551
				break;
552
			case EXOP_EQUAL:		// a == b
553
				valueStack.push_back(arg[1]==arg[0]);
554
				break;
555
			case EXOP_NOTEQUAL:			// a != b
556
				valueStack.push_back(arg[1]!=arg[0]);
557
				break;
558
			case EXOP_BITAND:			// a&b
559
				valueStack.push_back(arg[1]&arg[0]);
560
				break;
561
			case EXOP_XOR:			// a^b
562
				valueStack.push_back(arg[1]^arg[0]);
563
				break;
564
			case EXOP_BITOR:			// a|b
565
				valueStack.push_back(arg[1]|arg[0]);
566
				break;
567
			case EXOP_LOGAND:			// a && b
568
				valueStack.push_back(arg[1]&&arg[0]);
569
				break;
570
			case EXOP_LOGOR:			// a || b
571
				valueStack.push_back(arg[1]||arg[0]);
572
				break;
573
			case EXOP_TERTIF:			// darf so nicht vorkommen
574
				return false;
575
			case EXOP_TERTELSE:			// exp ? exp : exp, else muss zuerst kommen!
576
				if (exp[num++].second != EXOP_TERTIF)
577
				{
578
					expressionError = "Invalid tertiary operator";
579
					return false;
580
				}
581
				valueStack.push_back(arg[2]?arg[1]:arg[0]);
582
				break;
583
			}
584
			break;
585
		}
586
	}
587

588
	if (valueStack.size() != 1) return false;
589
	dest = valueStack[0];
590
	return true;
591
}
592

593
bool parseExpression(const char *exp, IExpressionFunctions *funcs, uint32_t &dest) {
594
	PostfixExpression postfix;
595
	if (initPostfixExpression(exp,funcs,postfix) == false) return false;
596
	return parsePostfixExpression(postfix,funcs,dest);
597
}
598

599
const char *getExpressionError()
600
{
601
	if (expressionError.empty())
602
		expressionError = "Invalid expression";
603
	return expressionError.c_str();
604
}
605

606
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

Product

Resources

Company
