c++ - C++中前缀表达式的递归评估

Question

<分区>

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