3

我刚刚通过以下问题为研究生 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++。有 1 年的实习经验和 1 年的 C++ 学术经验，但我还没有为其中一些测试做好准备。是否有任何推荐的资源可以让我尝试解决诸如此类的问题以获得更多的“测试”经验？

4

5 回答 5

2

这里的问题主要是解析，这可能会在第二年或第三年的编译器课程中涵盖。一旦您可以解析表达式以构建表示输入的递归数据结构（称为语法树），评估此类表达式就非常简单了。一个像样的递归解析器也可以在不实际构建语法树的情况下评估表达式。

要获得完整的治疗，您需要一本关于编译器的书，例如 Dragon book。IIRC 的《Programming: Principals and Practice using C++ 》一书涵盖了这样的示例。

您也可以等待《计算机编程艺术》第十章出版，其中将介绍解析。它计划在 2020 年左右推出。

于 2012-06-23T19:50:11.943 回答
1

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

代码非常简单，假设您至少粗略熟悉基本的递归下降解析技术。

#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);
}
于 2012-06-23T20:12:39.153 回答
1

从一个简单的语法开始：

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;
}
于 2012-06-23T23:55:07.540 回答
1

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

  1. 寻找一个数字：
    • 如果你看到一个数字压入堆栈
    • 如果你看到一个 '(' 将它推入堆栈并转到 1
    • 否则出错。
  2. 寻找一个操作：
    • 如果你看到一个操作将它推入堆栈
    • 否则报错
  3. 寻找一个数字：
    • 如果你看到一个数字压入堆栈
    • 如果你看到一个 '(' 推入堆栈并转到 1
    • 否则报错
  4. 从堆栈中弹出最后三个项目（应该是数字操作号）
    • 执行操作并将结果压入堆栈。
  5. 现在复杂一点：
    • 如果下一个字符转到下面的“PopCode” ，请查看下一个字符是否为')' 。
  6. 如果没有更多输入转到 7。
    • 否则转到 2
  7. 如果堆栈上只有一个项目，您就有了结果。
    • 否则出错。

流行代码

  1. 从堆栈中弹出最后两个值。应该是'（数字'
    • 如果不是，则错误
  2. 扔掉'（'
  3. 如果栈顶是一个 op push 值goto 4（上图）
  4. 否则将值压入堆栈goto 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
于 2012-06-23T21:14:57.733 回答
0

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

于 2012-06-23T20:06:12.163 回答