fork(1) download 
  1. #include <assert.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5.  
  6. // ================================
  7. //   Simple expression evaluator
  8. // ================================
  9.  
  10. // Error codes
  11. enum EXPR_EVAL_ERR {
  12. 	EEE_NO_ERROR = 0,
  13. 	EEE_PARENTHESIS = 1,
  14. 	EEE_WRONG_CHAR = 2,
  15. 	EEE_DIVIDE_BY_ZERO = 3
  16. };
  17.  
  18. typedef char EVAL_CHAR;
  19.  
  20. class ExprEval {
  21. private:
  22. 	EXPR_EVAL_ERR _err;
  23. 	EVAL_CHAR* _err_pos;
  24. 	int _paren_count;
  25.  
  26. 	// Parse a number or an expression in parenthesis
  27. 	double ParseAtom(EVAL_CHAR*& expr) {
  28. 		// Skip spaces
  29. 		while(*expr == ' ')
  30. 			expr++;
  31.  
  32. 		// Handle the sign before parenthesis (or before number)
  33. 		bool negative = false;
  34. 		if(*expr == '-') {
  35. 			negative = true;
  36. 			expr++;
  37. 		}
  38. 		if(*expr == '+') {
  39. 			expr++;
  40. 		}
  41.  
  42. 		// Check if there is parenthesis
  43. 		if(*expr == '(') {
  44. 			expr++;
  45. 			_paren_count++;
  46. 			double res = ParseSummands(expr);
  47. 			if(*expr != ')') {
  48. 				// Unmatched opening parenthesis
  49. 				_err = EEE_PARENTHESIS;
  50. 				_err_pos = expr;
  51. 				return 0;
  52. 			}
  53. 			expr++;
  54. 			_paren_count--;
  55. 			return negative ? -res : res;
  56. 		}
  57.  
  58. 		// It should be a number; convert it to double
  59. 		char* end_ptr;
  60. 		double res = strtod(expr, &end_ptr);
  61. 		if(end_ptr == expr) {
  62. 			// Report error
  63. 			_err = EEE_WRONG_CHAR;
  64. 			_err_pos = expr;
  65. 			return 0;
  66. 		}
  67. 		// Advance the pointer and return the result
  68. 		expr = end_ptr;
  69. 		return negative ? -res : res;
  70. 	}
  71.  
  72. 	// Parse multiplication and division
  73. 	double ParseFactors(EVAL_CHAR*& expr) {
  74. 		double num1 = ParseAtom(expr);
  75. 		for(;;) {
  76. 			// Skip spaces
  77. 			while(*expr == ' ')
  78. 				expr++;
  79. 			// Save the operation and position
  80. 			EVAL_CHAR op = *expr;
  81. 			EVAL_CHAR* pos = expr;
  82. 			if(op != '/' && op != '*')
  83. 				return num1;
  84. 			expr++;
  85. 			double num2 = ParseAtom(expr);
  86. 			// Perform the saved operation
  87. 			if(op == '/') {
  88. 				// Handle division by zero
  89. 				if(num2 == 0) {
  90. 					_err = EEE_DIVIDE_BY_ZERO;
  91. 					_err_pos = pos;
  92. 					return 0;
  93. 				}
  94. 				num1 /= num2;
  95. 			}
  96. 			else
  97. 				num1 *= num2;
  98. 		}
  99. 	}
  100.  
  101. 	// Parse addition and subtraction
  102. 	double ParseSummands(EVAL_CHAR*& expr) {
  103. 		double num1 = ParseFactors(expr);
  104. 		for(;;) {
  105. 			// Skip spaces
  106. 			while(*expr == ' ')
  107. 				expr++;
  108. 			EVAL_CHAR op = *expr;
  109. 			if(op != '-' && op != '+')
  110. 				return num1;
  111. 			expr++;
  112. 			double num2 = ParseFactors(expr);
  113. 			if(op == '-')
  114. 				num1 -= num2;
  115. 			else
  116. 				num1 += num2;
  117. 		}
  118. 	}
  119.  
  120. public:
  121. 	double Eval(EVAL_CHAR* expr) {
  122. 		_paren_count = 0;
  123. 		_err = EEE_NO_ERROR;
  124. 		double res = ParseSummands(expr);
  125. 		// Now, expr should point to '\0', and _paren_count should be zero
  126. 		if(_paren_count != 0 || *expr == ')') {
  127. 			_err = EEE_PARENTHESIS;
  128. 			_err_pos = expr;
  129. 			return 0;
  130. 		}
  131. 		if(*expr != '\0') {
  132. 			_err = EEE_WRONG_CHAR;
  133. 			_err_pos = expr;
  134. 			return 0;
  135. 		}
  136. 		return res;
  137. 	};
  138. 	EXPR_EVAL_ERR GetErr() {
  139. 		return _err;
  140. 	}
  141. 	EVAL_CHAR* GetErrPos() {
  142. 		return _err_pos;
  143. 	}
  144. };
  145.  
  146. // =======
  147. //  Tests
  148. // =======
  149.  
  150. #ifdef _DEBUG
  151. void TestExprEval() {
  152. 	ExprEval eval;
  153. 	// Some simple expressions
  154. 	assert(eval.Eval("1234") == 1234 && eval.GetErr() == EEE_NO_ERROR);
  155. 	assert(eval.Eval("1+2*3") == 7 && eval.GetErr() == EEE_NO_ERROR);
  156.  
  157. 	// Parenthesis
  158. 	assert(eval.Eval("5*(4+4+1)") == 45 && eval.GetErr() == EEE_NO_ERROR);
  159. 	assert(eval.Eval("5*(2*(1+3)+1)") == 45 && eval.GetErr() == EEE_NO_ERROR);
  160. 	assert(eval.Eval("5*((1+3)*2+1)") == 45 && eval.GetErr() == EEE_NO_ERROR);
  161.  
  162. 	// Spaces
  163. 	assert(eval.Eval("5 * ((1 + 3) * 2 + 1)") == 45 && eval.GetErr() == EEE_NO_ERROR);
  164. 	assert(eval.Eval("5 - 2 * ( 3 )") == -1 && eval.GetErr() == EEE_NO_ERROR);
  165. 	assert(eval.Eval("5 - 2 * ( ( 4 )  - 1 )") == -1 && eval.GetErr() == EEE_NO_ERROR);
  166.  
  167. 	// Sign before parenthesis
  168. 	assert(eval.Eval("-(2+1)*4") == -12 && eval.GetErr() == EEE_NO_ERROR);
  169. 	assert(eval.Eval("-4*(2+1)") == -12 && eval.GetErr() == EEE_NO_ERROR);
  170.  
  171. 	// Fractional numbers
  172. 	assert(eval.Eval("1.5/5") == 0.3 && eval.GetErr() == EEE_NO_ERROR);
  173. 	assert(eval.Eval("1/5e10") == 2e-11 && eval.GetErr() == EEE_NO_ERROR);
  174. 	assert(eval.Eval("(4-3)/(4*4)") == 0.0625 && eval.GetErr() == EEE_NO_ERROR);
  175. 	assert(eval.Eval("1/2/2") == 0.25 && eval.GetErr() == EEE_NO_ERROR);
  176. 	assert(eval.Eval("0.25 * .5 * 0.5") == 0.0625 && eval.GetErr() == EEE_NO_ERROR);
  177. 	assert(eval.Eval(".25 / 2 * .5") == 0.0625 && eval.GetErr() == EEE_NO_ERROR);
  178.  
  179. 	// Repeated operators
  180. 	assert(eval.Eval("1+-2") == -1 && eval.GetErr() == EEE_NO_ERROR);
  181. 	assert(eval.Eval("--2") == 2 && eval.GetErr() == EEE_NO_ERROR);
  182. 	assert(eval.Eval("2---2") == 0 && eval.GetErr() == EEE_NO_ERROR);
  183. 	assert(eval.Eval("2-+-2") == 4 && eval.GetErr() == EEE_NO_ERROR);
  184.  
  185. 	// === Errors ===
  186. 	// Parenthesis error
  187. 	eval.Eval("5*((1+3)*2+1");
  188. 	assert(eval.GetErr() == EEE_PARENTHESIS && strcmp(eval.GetErrPos(), "") == 0);
  189. 	eval.Eval("5*((1+3)*2)+1)");
  190. 	assert(eval.GetErr() == EEE_PARENTHESIS && strcmp(eval.GetErrPos(), ")") == 0);
  191.  
  192. 	// Repeated operators (wrong)
  193. 	eval.Eval("5*/2");
  194. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "/2") == 0);
  195.  
  196. 	// Wrong position of an operator
  197. 	eval.Eval("*2");
  198. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "*2") == 0);
  199. 	eval.Eval("2+");
  200. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "") == 0);
  201. 	eval.Eval("2*");
  202. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "") == 0);
  203.  
  204. 	// Division by zero
  205. 	eval.Eval("2/0");
  206. 	assert(eval.GetErr() == EEE_DIVIDE_BY_ZERO && strcmp(eval.GetErrPos(), "/0") == 0);
  207. 	eval.Eval("3+1/(5-5)+4");
  208. 	assert(eval.GetErr() == EEE_DIVIDE_BY_ZERO && strcmp(eval.GetErrPos(), "/(5-5)+4") == 0);
  209. 	eval.Eval("2/"); // Erroneously detected as division by zero, but that's ok for us
  210. 	assert(eval.GetErr() == EEE_DIVIDE_BY_ZERO && strcmp(eval.GetErrPos(), "/") == 0);
  211.  
  212. 	// Invalid characters
  213. 	eval.Eval("~5");
  214. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "~5") == 0);
  215. 	eval.Eval("5x");
  216. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "x") == 0);
  217.  
  218. 	// Multiply errors
  219. 	eval.Eval("3+1/0+4$"); // Only one error will be detected (in this case, the last one)
  220. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "$") == 0);
  221. 	eval.Eval("3+1/0+4");
  222. 	assert(eval.GetErr() == EEE_DIVIDE_BY_ZERO && strcmp(eval.GetErrPos(), "/0+4") == 0);
  223. 	eval.Eval("q+1/0)"); // ...or the first one
  224. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "q+1/0)") == 0);
  225. 	eval.Eval("+1/0)");
  226. 	assert(eval.GetErr() == EEE_PARENTHESIS && strcmp(eval.GetErrPos(), ")") == 0);
  227. 	eval.Eval("+1/0");
  228. 	assert(eval.GetErr() == EEE_DIVIDE_BY_ZERO && strcmp(eval.GetErrPos(), "/0") == 0);
  229.  
  230. 	// An emtpy string
  231. 	eval.Eval("");
  232. 	assert(eval.GetErr() == EEE_WRONG_CHAR && strcmp(eval.GetErrPos(), "") == 0);
  233. }
  234. #endif
  235.  
  236. // ============
  237. // Main program
  238. // ============
  239.  
  240. int main() {
  241. #ifdef _DEBUG
  242. 	TestExprEval();
  243. #endif
  244. 	static const char *errors[] = {
  245. 		"no error",
  246. 		"parentheses don't match",
  247. 		"invalid character",
  248. 		"division by zero"};
  249.  
  250. 	puts("Enter an expression (or an empty string to exit):");
  251. 	for(;;) {
  252. 		// Get a string from console
  253. 		static char buff[256];
  254. 		char *expr = gets_s(buff, sizeof(buff));
  255.  
  256. 		// If the string is empty, then exit
  257. 		if(*expr == '\0')
  258. 			return 0;
  259.  
  260. 		// Evaluate the expression
  261. 		ExprEval eval;
  262. 		double res = eval.Eval(expr);
  263. 		if(eval.GetErr() != EEE_NO_ERROR) {
  264. 			printf("  Error: %s at %s\n", errors[eval.GetErr()], eval.GetErrPos());
  265. 		} else {
  266. 			printf("  = %g\n", res);
  267. 		}
  268. 	}
  269. }
  270.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:254:41: error: ‘gets_s’ was not declared in this scope
   char *expr = gets_s(buff, sizeof(buff));
                                         ^
stdout 
Standard output is empty
https://ideone.com/M8vRgg
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!