C解析器递归

Question

我正在用 C 和 Lisp 算术计算器编写一个简单的程序，只涉及整数和 "+ - */" 运算符，我这样做是为了学习目的，这不是我的家庭作业或类似的东西那个。

所以我创建了一个函数，可以正确解析像这样的 (+ 2 3) 它会输出 5，所以我知道如何处理非嵌套语句但是当我有这样的东西时怎么办(+ (* 2 3) (- 4 2)) 所以我似乎可以使用递归来解决这个问题，但我真的不知道该怎么做。

我的逻辑如下(伪代码):`

  function parse_line(int n)
    get_input(string);
    if string[n] == '('
     if string[n+1] == operator
      if string[n+3] == number
       result = parseAllNumbers(); //between ( )
       return result; 
    if string[n+3] == '('
     parse_line(n+2);

`

所以我的逻辑在这里是正确的，如果我有 (+ (* 2 3) (- 4 2)) 我会计算。 (* 2 3)，我将如何计算 (- 4 2) 然后将这两个结果相加

Answer 1

您绝对是在正确的轨道上。

假设我们编写了一个 getToken() 函数，它从当前位置读取字符串中的下一个逻辑标记。逻辑标记可以是数字、“(”、“)”或四个运算符中的任何一个。然后我们可以递归地评估表达式。

function evaluateExpression(){
    var token = getToken();

    if( isNumber(token)){
        return token;
    }else if( isOpenParen(token)){
        return evaluateExpression();
    }

    var numOne = evaluateExpression();
    var nextToken = null;
    while( !isRightParen(nextToken)){
        nextToken = getToken();
        numOne = evaluate(token, numOne, nextToken);
    }

    return numOne;
}

函数 isNumber() 和 isLeftParen() 做它们所暗示的事情，如果传递给它的标记分别是数字或左括号，则返回 true。 evaluate() 函数采用运算符标记以及两个数字来评估它们。例如，evaluate(+,2,4) 将返回 6 而 evaluate(-,2,4) 将返回 2.