评估一个简单的字符串数学表达式

Question

我刚刚参加了以下问题的研究生C++开发人员的测试。它没有做得太好，因为我无法确定完成任务的明确方式。时间限制也没有帮助。我感兴趣的是如何经验的开发人员会解决后续问题 - 伪或示例代码：

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 (e.g. 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) 

此外，这是第二个C++，我已经未能成功完成。使用C++已经有1年的跨学科经验和1年的学术经验，但我没有准备好进行这些测试。有没有推荐的资源可以帮助我解决诸如此类问题，以获得更多的“测试”体验？

Answer 1

这里的问题主要是解析，这可能会在第二年或第三年编译器课程中介绍。一旦你可以解析表达式来构建一个代表输入的递归数据结构（称为语法树），评估这样的表达式就相当简单了。递归体面分析器也可以在不实际构建语法树的情况下评估表达式。

对于一个完整的治疗，你会想要一本关于编译器的书，比如龙书。另外IIRC的书编程：使用C++的校长和实践涵盖了一个这样的例子。

您还可以等待第十章的计算机编程艺术发布，其中将包括解析。它计划在2020年前后出现。

Answer 2

解决（不一定）简单数学表达式的最简单方法是使用Shunting Yard algorithm将其转换为Reverse Polish Notation，这对于使用堆栈进行解析几乎是微不足道的。当然，对于任务或面试来说这样做可能是不可行的（也许除非有一个SY算法参考可用）。

Answer 3

这是我最短的尝试。花了大约40分钟打字，你可以在ideone上玩（link）。

该代码非常简单，假设您至少对基本recursive descent parsing技术有一个粗略的熟悉。

#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 4

这是一个简单的扫描推适用（扭曲是大括号）。

1. 查找一个数字：
   • 如果你看到一些推入堆栈
   • 如果你看到一个“（”推入堆栈和转到1
   • 否则错误。
2. 查找运算：
   • 如果你看到一个运算推到堆栈
   • 否则错误
3. 查找一个数字：
   • 如果你看到一个数字推入堆栈
   • 如果您看到'（'推入堆栈并且转到1
   • 否则错误
4. 弹出过去三年从栈中的项目（应该是数字运算次数）
   
   • 做了手术，结果压入堆栈。
5. 现在复杂位：
   • 偷看，看是否下一个字符是一个“）”如果是转到“Pop代码”下方。
6. 如果不再输入转到7。
   • Otherewise 转到2
7. 如果只有一个堆栈上的项目你有你的结果。
   • 否则会报错。

Pop代码

1. 流行过去两年从堆栈值。应该是“（编号”
   • 如果它不是，则一个错误
2. 扔掉“（”
3. 如果堆栈的顶部是转到4（以上运算推值）
4. 否则推值压入堆栈转到图5（上图）

完成时，应该有一个堆栈上一个号码。

例子：

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 5

开始一个简单的语法：

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

这可能是问题的最大障碍。你希望能够编写一个简单的自顶向下的递归下降解析器，所以你的语法需要以一种方式写入，以允许这种情况发生。

然后从那里实现是相当简单：

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; 
}