评估一个简单的字符串数学表达式 [英] Evaluate a simple string mathematical expression

问题描述

我刚刚为一个毕业的C ++开发人员进行了测试，涉及以下问题。进行得并不顺利，因为我无法确定完成任务的明确方法。时间限制也无济于事。我对经验丰富的开发人员如何解决以下问题（使用伪代码或示例代码）感兴趣：

I've just taken a test for a graduate C++ developer with the question below. It didn't go too well as I couldn't decide on a clear way of completing the task. Time limit didn't help either. I'm interested in how experienced developers would have tackled the follow 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 (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 ++，但我还没有为某些测试做好准备，是否有任何推荐的资源可以让我解决这些问题，从而获得更多的测试经验？

In addition, this is the 2nd C++ that I've failed to complete successfully. Have had 1 year intership experiece and 1 year academic experiece using C++, but I'm not prepared for some of these tests. Are there any recommended resources where I can attept to solve problems such as this one in order to gain more 'testing' experience?

推荐答案

这里的问题主要是解析，可能在第二年或第三年的编译器课程中都会涉及到。一旦您可以解析表达式以构建表示输入（称为语法树）对于评估此类表达式而言是微不足道的。体面的解析器还可以在不实际构建语法树的情况下评估表达式。

The problem here is mostly parsing, which would be covered in a compiler course probably in second or third year. Once you can parse expressions to build up a recursive data structure representing the input (called a syntax tree) it's pretty trivial to evaluate such expressions. A recursive decent parser can also evaluate the expression as it goes without actually building a syntax tree.

要进行全面处理，您需要一本有关编译器的书，例如Dragon书。 IIRC的《编程：使用C ++的原理和实践》一书也涵盖了这样的例子。

For a full treatment you'd want a book on compilers, such as the dragon book. Also IIRC the book Programming: Principals and Practice using C++ covers an example like this.

您还可以等待的第十章即将出版的《计算机编程艺术》将涵盖解析。计划在2020年左右推出。

You could also wait for chapter ten of The Art of Computer Programming to be published, which will cover parsing. It's scheduled to be out around 2020.

这篇关于评估一个简单的字符串数学表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！