c++ - 単純な文字列の数式を評価する

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)

さらに、これは私が正常に完了できなかった 2 番目の C++ です。C++ を使用して 1 年間のインターンシップ経験と 1 年間のアカデミックな経験がありましたが、これらのテストのいくつかに対する準備ができていません。「テスト」の経験を積むために、このような問題の解決を試みることができる推奨リソースはありますか?

Answer 1

ここでの問題は主に構文解析であり、おそらく2年目または3年目にコンパイラーコースでカバーされます。式を解析して、入力を表す再帰的なデータ構造（構文ツリーと呼ばれる）を構築できたら、そのような式を評価するのは非常に簡単です。再帰下降パーサーは、実際に構文ツリーを構築せずに、式をそのまま評価することもできます。

完全な治療のためには、ドラゴンブックなどのコンパイラに関する本が必要です。また、IIRCの本Programming：Principals and Practice using C ++は、このような例をカバーしています。

また、構文解析について説明するThe Art ofComputerProgrammingの第10章が公開されるのを待つこともできます。2020年頃に発売される予定です。

Answer 2

これが私の最短の試みです。入力するのに約 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);
}

Answer 3

これは単純なスキャン プッシュ適用です (ツイストはブレースです)。

1. 番号を探します:
   • 数字がスタックにプッシュされている場合
   • 「(」が表示された場合は、それをスタックにプッシュして1に移動します
   • それ以外の場合はエラーです。
2. op を探します。
   • op が表示されたら、それをスタックにプッシュします
   • そうでなければエラー
3. 番号を探します:
   • 数字がスタックにプッシュされている場合
   • 「(」が表示された場合は、スタックにプッシュして1に移動します
   • そうでなければエラー
4. スタックから最後の 3 つのアイテムをポップします (number op number である必要があります)
   
   • 操作を実行し、結果をスタックにプッシュします。
5. 複雑なビット：
   • 次の文字が')'であるかどうかを確認するには、下の「PopCode」に移動します。
6. これ以上入力がない場合は、7 に進みます。
   • それ以外の場合は2に進みます
7. スタックにアイテムが 1 つしかない場合は、結果が得られます。
   • それ以外の場合はエラーです。

ポップコード

1. スタックから最後の 2 つの値をポップします。'( Number' である必要があります
   • そうでない場合はエラー
2. 「(」を捨てる
3. スタックの一番上が op プッシュ値の場合は4 に進みます (上記)
4. それ以外の場合は、値をスタックgoto 5 (上記)にプッシュします。

終了すると、スタックに 1 つの数値が存在するはずです。

例：

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

簡単な文法から始めます。

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

Answer 5

(必ずしもそうであるとは限りませんが) 単純な数式を解く最も簡単な方法は、Shunting Yard アルゴリズムを使用して逆ポーランド記法に変換することです。これは、スタックを使用して解析するのはほとんど簡単です。もちろん、課題や面接のためにそうするのは現実的ではないかもしれません (おそらく、SY アルゴリズムのリファレンスが利用可能でない限り)。