字符串表达式递归下降计算器：幂运算错误与右结合问题排查

问题说明 #

你用递归下降法实现的表达式计算器，加减乘除、括号解析功能正常，但幂运算存在两个问题：

• 实现逻辑错误，无法正确计算底数的指数次幂
• 未处理幂运算的右结合特性，比如输入3^1^2时，程序输出9（按左结合计算(3^1)^2），但正确结果应为3（按右结合计算3^(1^2)）

错误根源 #

1. 幂运算逻辑错误：原mult_div函数中，用for(int k=0;k<power(); k++, a*=power())计算幂的方式完全错误——每次循环都调用power()会重复读取输入流中的字符，导致指数部分被多次解析，计算逻辑也不符合幂运算的定义（应该是底数自乘指数次，而不是每次乘新解析的数值）。
2. 右结合未处理：加减乘除是左结合运算符，用while循环累积结果是正确的，但幂运算属于右结合，必须用递归方式处理，才能保证a^b^c解析为a^(b^c)而非(a^b)^c。

修复后的完整代码 #

#include <stdio.h>
#include <setjmp.h>

jmp_buf begin;
char curlex;

void getlex(void);
int expr(void);
int add_sub(void);
int mult_div(void);
int power(void);
int exponentiate(int base, int exp); // 新增幂运算计算函数
void error();

int main() {
    int result;
    setjmp(begin);
    printf("==>");
    getlex();
    result = expr();
    if (curlex != '\n') error();
    printf("\n%d\n", result);
    return 0;
}

void getlex() {
    while ((curlex = getchar()) == ' ');
}

void error(void) {
    printf("\nERROR!\n");
    while (getchar() != '\n');
    longjmp(begin, 1);
}

int expr() {
    int e = add_sub();
    while (curlex == '+' || curlex == '-') {
        if (curlex == '+') {
            getlex();
            e += add_sub();
        } else if (curlex == '-') {
            getlex();
            e -= add_sub();
        }
    }
    return e;
}

int add_sub() {
    int a = mult_div();
    while (curlex == '*' || curlex == '/') {
        if (curlex == '*') {
            getlex();
            a *= mult_div();
        } else if (curlex == '/') {
            getlex();
            a /= mult_div();
        }
    }
    return a;
}

int mult_div() {
    int a = power();
    // 移除原错误的幂运算逻辑，把幂运算交给power函数处理
    return a;
}

int power() {
    int m;
    switch(curlex) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9': 
            m = curlex - '0'; 
            getlex();
            break;
        case '(': 
            getlex(); 
            m = expr();
            if (curlex == ')') {
                getlex();
                break;
            } else {
                error();
            }
        default: 
            error();
    }

    // 处理右结合的幂运算：如果下一个是^，递归计算右边的幂作为指数
    while (curlex == '^') {
        getlex();
        int exp = power();
        m = exponentiate(m, exp);
    }
    return m;
}

// 实现正确的整数幂运算：base^exp
int exponentiate(int base, int exp) {
    int result = 1;
    for (int i = 0; i < exp; i++) {
        result *= base;
    }
    return result;
}

修复说明 #

1. 新增exponentiate函数：专门负责计算整数的幂运算，输入底数和指数，返回base^exp的结果，避免重复解析输入流。
2. 调整幂运算处理逻辑：把幂运算从mult_div移到power函数中，利用递归实现右结合——当遇到^时，先递归解析右边的幂运算结果作为指数，再计算当前底数的该指数次幂。
3. 修正解析流程：在power函数中，解析完底数后，检查是否有^运算符，若有则递归处理右侧表达式，保证右结合优先级。

现在测试3^1^2，程序会先计算1^2=1，再计算3^1=3，符合预期结果。

内容的提问来源于stack exchange，提问作者Stepan Sokol