0

次のタイプの式を評価する再帰アルゴリズムをC++で記述しようとしています： "operator" "variable" "variable"（例：input = + 3 4; output = 7）。演算子は基本的なもの（+、-、*、/）であり、変数は1から9までの整数です。問題は、開始方法と使用する方法がわからないことです。スタックやリストを使用できません。

編集：私はC ++の紹介の試験のために勉強しているので、問題を解決するために複雑な方法を使用することは許可されていません。プロシージャ、ループ、再帰、検索およびスレッドの方法しか使用できません。

ありがとう。

4

4 に答える 4

2

（明らかに）二項演算子のみを扱っているため、これはかなり簡単です（1つの注意点があります：明示的にスタックを使用することはありませんが、再帰のほとんどすべての正常な実装は暗黙的にスタックを使用します）。

基本的なパターンは次のようになります。

int apply(char op, int a, int b) {
    switch (op) { 
       case '+': return a + b;
       case '-': return a - b;
       case '/': return a / b;
       case '*': return a * b;
       default: throw bad_operator(op);
    }
}   

int expression(char *&input) {
    char op = *input++;

    if (isdigit(op)) 
       return op - '0';

    int a = expression(input);
    int b = expression(input);
    return apply(op, a, b);
}

クイックテストプログラム:

#include <ctype.h>
#include <iostream>
#include <exception>
#include <string>

struct bad_operator : public std::logic_error { 
    bad_operator(char ch)  : 
        std::logic_error(std::string("Bad operator: ") + ch) 
    {}
};

int main() {
    char *input="+/42-43";
    std::cout << expression(input);
    return 0;
}
于 2013-01-09T05:47:16.667 に答える
1

このようにしてみてください。擬似コード:

double Process(Parser & parser)
{
    Token token = parser.GetToken();

    if (token.Type == number)
        return (NumberToken)token.value;
    else if (token.Type == operator)
    {
        double left = Process(parser);
        double right = Process(parser);

        switch (OperatorToken)token.op:
        {
        case '+' :
            {
                return left + right;
            }
        // ...
        }
    }
}

ただし、この種の問題は、スタックを使用するとより簡単に解決できます。

于 2013-01-09T05:44:54.180 に答える
1

再帰を使用したソリューションを次に示します (式に空白を使用できません)。

#include <cstdio>

int eval(const char *s, const char **outptr)
{
    int a, b, y;
    const char *out;

    switch (*s) {
    case '+':
        a = eval(s + 1, &out);
        b = eval(out, &out);
        y = a + b;
        *outptr = out;
        break;
    case '-':
        a = eval(s + 1, &out);
        b = eval(out, &out);
        y = a - b;
        *outptr = out;
        break;
    case '*':
        a = eval(s + 1, &out);
        b = eval(out, &out);
        y = a * b;
        *outptr = out;
        break;
    case '/':
        a = eval(s + 1, &out);
        b = eval(out, &out);
        y = a / b;
        *outptr = out;
        break;
    default: /* '0'...'9'assumed */
        y = *s - '0';
        *outptr = s + 1;
        break;
    }

    return y;
}

int main(int argc, char *argv[])
{
    const char *end;
    int x;

    x = eval(argv[1], &end);
    printf("%d\n", x);

    return 0;
}

例：

./eval +3+*45/62
26
于 2013-01-09T05:52:11.193 に答える
0

入力反復子 (入力文字列へのポインターやベクトル反復子など) があると仮定すると、次のようなものを使用できます。

compute (input.iterator it) {
  if (it != input.end() and is_operator(*it)) {
     operator op = *it;
     int v1, v2;
     it++;
     v1 = is_operator(*it) ? compute(it) : *it;
     it++;
     v2 = is_operator(*it) ? compute(it) : *it;
     return operator_exec(op, v1, v2) 
  }
  return *it;
}
于 2013-01-09T05:48:17.143 に答える