Оценка арифметического выражения с использованием рекурсии в C

Question

Вот алгоритм для вычисления арифметического выражения с использованием рекурсии :

• Найти операнд1
• t1 = Eval (операнд1)
• Найти операнд2
• t2 = Eval (операнд2)
• Применить оператор к t1 и t2

Предположения:

• каждый операнд находится между двумя операторами

• есть только двоичные операции

• для каждой операции есть круглые скобки (включая внешние скобки)

Введите:

• массив токенов, представляющих арифметическое выражение

• num_tokens - количество токенов

Пример массива токенов: {"(", "9", "+", "(", "50", "-", "25", ")", ")"}

Я пытался реализовать алгоритм, но моя программа не запускается (выходное состояние -1 - единственное сообщение, которое я получаю). Почему это происходит?

int apply(char op, int a, int b) {
       if (op == '+'){
        printf("%d %c %d\n", a,op,b);
        return a + b;
       }
       else if (op == '-'){
        printf("%d %c %d\n", a,op,b);
        return a - b;
       }
       else if(op == '/'){
        printf("%d %c %d\n", a,op,b);
        return a / b;
       }
       else if(op == '*'){
        printf("%d %c %d\n", a,op,b);
        return a * b;
       }
}   

int eval_tokens(char** expression, int num_tokens)
{
  // implement me
    int index;
    int opIndex = find_operator(expression, num_tokens); //find index of operator
    int count1=0,count2=0,term1,term2,i,j;

    if(*expression[0] == '(')
      i = 1;
    else
      i = 0;

    while(i <= opIndex){
        i++;
        count1++;
    }

    term1 = eval_tokens(expression+1,count1);

    j = opIndex+1;
    while(j < num_tokens){
      count2++;
      j++;
    }

  term2 = eval_tokens(expression+opIndex+1,count2); //expression+opIndex+1 points to index after opIndex
  return apply(*expression[opIndex], term1, term2);
}

int main(void) {
    char*expression[] = {"(", "(", "5", "+", "3", ")", "-", "(", "2", "+", "1", ")", ")"};
    printf("result = %d\n", eval_tokens(expression, 13));
    return 0;
}

Answer 1

Чтобы использовать str (или expression) в качестве стека, из которого можно извлекать элементы, я бы сделал эти аргументы «изменяемыми» в рекурсивной функции. Следовательно, вы могли бы ввести вторую функцию int eval_tokens_recursive(char*** expression, int *num_tokens), которая имеет еще один уровень косвенности и может фактически «брать элементы из стека», изменяя значения аргументов.

Код может выглядеть следующим образом. Надеюсь, это поможет.

int eval_tokens_recursive(char*** expression, int *num_tokens) {

    char *token = **expression;
    if (*num_tokens == 0) {
        printf("expecting more tokens.\n");
        exit(1);
    }
    if (*token == '(') { // begin of expression?
        (*expression)++;  // skip opening brace
        (*num_tokens)--;

        // lhs
        int lhs = eval_tokens_recursive(expression, num_tokens);

        // operand
        char operand = ***expression;
        (*expression)++;
        (*num_tokens)--;

        // rhs
        int rhs = eval_tokens_recursive(expression, num_tokens);

        (*expression)++;  // skip closing brace
        (*num_tokens)--;

        switch (operand) {
            case '+':
                return lhs + rhs;
            case '-':
                return lhs - rhs;
            case '*':
                return lhs * rhs;
            case '/':
                return lhs / rhs;
            default:
                return 0;
        }

    } else { // not an expression; must be a numeric token
        int operand;
        if (sscanf(token, "%2d", &operand) != 1) {
            printf("expecting numeric value; cannot parse %s.\n", token);
            exit(1);
        }
        (*expression)++;
        (*num_tokens)--;
        return operand;
    }

}

int eval_tokens(char** expression, int num_tokens) {
    return eval_tokens_recursive(&expression, &num_tokens);
}

int main() {

    char *expressions[] = {"(", "9", "+", "(", "50", "-", "25", ")", ")"};

    int result = eval_tokens(expressions, 9);

    printf("result: %d\n", result);

}