Appreciate the simple mathematical expression of a string

Question

I just passed the test for a C ++ graduate developer with the question below. This is not too good, since I could not decide how to do it. Timing did not help either. I am interested in how experienced developers could solve the following problem: in pseudo or sample code:

Evaluate Write a function in C or C++ that evaluates the result of a simple expression. The function should ignore whitespace, but stop at the first non valid character. Valid tokens are listed in the table below: 0-9 - Only integers are allowed in expressions () - Nested expressions should be evaluated first. +, -, *, / - Basic operators are addition, subtraction, multiplication and division. The expression should be parsed from left to right. It is not necessary to consider operator precedence in your solution (eg 1 + 3 * 4 = 16). If there is an error in the expression, the function should return false. Suggested prototype for function: Example: bool evaluate(const char *expression, int &result) { ... } **Input** 1+3 (1 + (12 * 2) **Result** 4 N/A **Return code** true false (missing bracket) 

Also, this is the second C ++ that I could not execute successfully. Had 1 year intersessional experience and 1 year academic experience using C ++, but I'm not ready for some of these tests. Are there any recommended resources where I can take some kind of problem, for example, to get more testing experience?

Answer 1

The problem here is mainly in the parsing, which will be considered in the course of the compiler, probably in the second or third year. After you can parse expressions to create a recursive data structure representing an input (called a syntax tree), it is quite difficult to evaluate such expressions. A recursive decent parser can also evaluate an expression as it goes without actually building a syntax tree.

For complete treatment, you need a book about compilers, for example, a book of dragons. Also, an example is the IIRC book, Programming: Principles and Practices Using C ++.

You can also wait until chapter ten, The Art of Computer Programming, is published, which will be devoted to analysis. It is planned for the period until 2020.

Answer 2

Here is my shortest attempt. It took about 40 minutes to dial, you can play with it on ideone ( link ).

The code is very simple, assuming you have at least a superficial familiarity with the basic recursive descent method .

 #include <iostream> #include <cctype> using namespace std; bool eval_expr(const char **pe, int &lhs, bool inside = false); // gets the next char after skipping optional whitespace char skip_ws(const char **pe) { while (**pe == ' ') ++(*pe); return **pe; } // evaluates a parenthesized expression or a number bool eval_prim(const char **pe, int &res) { char c = skip_ws(pe); if (c == '(') { ++(*pe); if (!eval_expr(pe, res, true)) return false; ++(*pe); return true; } if (isdigit(c)) { res = 0; while (isdigit(c)) { res = 10*res + c - '0'; c = *(++(*pe)); } return true; } return false; } // evaluates a chain of + - * / operations bool eval_expr(const char **pe, int &lhs, bool inside) { if (!eval_prim(pe, lhs)) return false; char op; while ((op = skip_ws(pe)) && (op == '+' || op == '-' || op == '*' || op == '/')) { ++(*pe); int rhs; if (!eval_prim(pe, rhs)) return false; switch (op) { case '+': lhs += rhs; break; case '-': lhs -= rhs; break; case '*': lhs *= rhs; break; case '/': lhs /= rhs; break; } } return inside ? op == ')' : !op; } // wrapper API to hide an extra level of indirection bool evaluate(const char *e, int &result) { return eval_expr(&e, result); } 

Answer 3

This is a simple scan load (a twist is braces).

• Find the number:
  • If you see a number pushing the stack
  • if you see '(' click on the stack and go 1
  • Otherwise a mistake.
• Look for op:
  • If you see op pushing it onto the stack
  • Otherwise error
• Find the number:
  • If you see a number pushing the stack
  • If you see '(' push on stack and goto 1
  • Otherwise error
• pop the last three elements from the stack (there must be a number number number number)
  
  • perform the operation and push the result onto the stack.
• Now for the hard bit:
  • Peek to see if the next character is ')' if it contains the "PopCode" below.
• If there is no more goto 7 input.
  • Regarding goto 2
• If only one item on the stack has your result.
  • Otherwise a mistake.

Popcode

• Print the last two values ​​from the stack. Must be '(Number'
  • If this is not a mistake,
• Drop the '('
• If the top of the stack is op push goto 4 (above)
• Otherwise, push the value onto the goto 5 stack (above)

Upon completion, there must be one number on the stack.

Example:

 1+3 Rule 1: push 1 stack = '1' Rule 2: push + stack = '1 +' Rule 3: push 3 stack = '1 + 3' Rule 4: pop and do: stack = '4' Rule 5: Nothing stack = '4' Rule 6: goto 7 stack = '4' Rule 7: stack = '4' (1 + (12 * 2) Rule 1: push ( goto 1 stack = '(' Rule 1: push 1 stack = '( 1' Rule 2: push + stack = '( 1 +' Rule 3: push ( goto 1 stack = '( 1 + (' Rule 1: push 12 stack = '( 1 + ( 12' Rule 2: push * stack = '( 1 + ( 12 *' Rule 3: push 2 stack = '( 1 + ( 12 * 2' Rule 4: Pop and do: stack = '( 1 + ( 24' Rule 5: Do 'PopCode' stack = '( 1 + ( 24' Pop 1: Pop 2 stack = '( 1 +' Pop 2: Holding 24 stack = '( 1 +' Pop 3: push 24 goto 4 stack = '( 1 + 24' Rule 4: Pop and do stack = '( 25' Rule 5: Nothing stack = '( 25' Rule 6: goto 7 stacj = '( 25' Rule 7: More than 1 item error Re-Doing with correct formula (1 + (12 * 2)) Rule 1: push ( goto 1 stack = '(' Rule 1: push 1 stack = '( 1' Rule 2: push + stack = '( 1 +' Rule 3: push ( goto 1 stack = '( 1 + (' Rule 1: push 12 stack = '( 1 + ( 12' Rule 2: push * stack = '( 1 + ( 12 *' Rule 3: push 2 stack = '( 1 + ( 12 * 2' Rule 4: Pop and do: stack = '( 1 + ( 24' Rule 5: Do 'PopCode' stack = '( 1 + ( 24' Pop 1: Pop 2 stack = '( 1 +' Pop 2: Holding 24 stack = '( 1 +' Pop 3: push 24 goto 4 stack = '( 1 + 24' Rule 4: Pop and do stack = '( 25' Rule 5: Do 'PopCode' stack = '( 25' Pop 1: Pop 2 stack = '' Pop 2: holding 25 stack = '' Pop 3: Nothing. stack = '' Pop 4: push 25 goto 5 stack = '25' Rule 5: Nothing stack = '25' Rule 6: goto 7 stack = '25' Rule 7: Result = 25 

Answer 4

Start with a simple grammar:

 expr: n-expr {o-expr} | p-expr {o-expr} n-expr: [0-9]n-expr p-expr: ( expr ) o-expr: op expr op: + | - | * | / 

This is probably the biggest hurdle to the question. You want to write a simple reverse down parser, so your grammar needs to be written for this to happen.

Then the implementation from there is quite simple:

 bool expr (const char *&s, int &result, int eos = 0) { while (isspace(*s)) ++s; if (*s == eos) return false; if (isdigit(*s)) { if (!n_expr(s, result)) return false; } else if (*s == '(') { if (!p_expr(s, result)) return false; } else return false; while (isspace(*s)) ++s; if (*s == eos) return true; return o_expr(s, result, eos); } bool n_expr (const char *&s, int &result) { int n = 0; while (isdigit(*s)) n = 10 * n + (*s++ - '0'); result = n; return true; } bool p_expr (const char *&s, int &result) { if (expr(++s, result, ')')) { ++s; return true; } return false; } bool o_expr (const char *&s, int &result, int eos) { int oresult = 0; const char *op = strchr("+-*/", *s); if (op == 0) return false; if (!expr(++s, oresult, eos)) return false; switch (*op) { case '+': result += oresult; break; case '-': result -= oresult; break; case '*': result *= oresult; break; case '/': result /= oresult; break; default: return false; } return true; } 

Answer 5

The easiest way to solve (not necessarily) a simple mathematical expression is to use the Shunting Yard algorithm to convert it to Reverse Polish Notation , which is almost trivial for stack analysis. Of course, it would be impossible to do this for a job or an interview (possibly if there is no reference to the SY algorithm).