C语言实现简单算术表达式求值：LR分析法和语法制导翻译法

以下是实现简单算术表达式求值的完整C语言代码，使用LR分析法和语法制导翻译法，通过两个栈（操作数栈和操作符栈）实现：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    int data[MAX_STACK_SIZE];
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_STACK_SIZE - 1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack is full.\n");
        exit(1);
    }
    s->data[++s->top] = value;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return s->data[s->top--];
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return s->data[s->top];
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int precedence(char c) {
    switch (c) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

int evaluate(char *expression) {
    Stack operandStack;
    Stack operatorStack;
    initStack(&operandStack);
    initStack(&operatorStack);

    int i = 0;
    while (expression[i] != '\0') {
        if (isdigit(expression[i])) {
            int value = 0;
            while (isdigit(expression[i])) {
                value = value * 10 + expression[i] - '0';
                i++;
            }
            push(&operandStack, value);
        } else if (isOperator(expression[i])) {
            while (!isEmpty(&operatorStack) && precedence(expression[i]) <= precedence(peek(&operatorStack))) {
                int op2 = pop(&operandStack);
                int op1 = pop(&operandStack);
                char op = pop(&operatorStack);
                switch (op) {
                    case '+':
                        push(&operandStack, op1 + op2);
                        break;
                    case '-':
                        push(&operandStack, op1 - op2);
                        break;
                    case '*':
                        push(&operandStack, op1 * op2);
                        break;
                    case '/':
                        push(&operandStack, op1 / op2);
                        break;
                }
            }
            push(&operatorStack, expression[i]);
            i++;
        } else {
            i++;
        }
    }

    while (!isEmpty(&operatorStack)) {
        int op2 = pop(&operandStack);
        int op1 = pop(&operandStack);
        char op = pop(&operatorStack);
        switch (op) {
            case '+':
                push(&operandStack, op1 + op2);
                break;
            case '-':
                push(&operandStack, op1 - op2);
                break;
            case '*':
                push(&operandStack, op1 * op2);
                break;
            case '/':
                push(&operandStack, op1 / op2);
                break;
        }
    }

    return pop(&operandStack);
}

int main() {
    char expression[100];
    printf("Enter an arithmetic expression: ");
    scanf("%s", expression);
    printf("Result: %d\n", evaluate(expression));
    return 0;
}

代码流程：

1. 初始化栈：创建两个栈，分别用于存储操作数和操作符。
2. 遍历表达式：逐个字符扫描表达式，并进行如下操作：
   • 数字: 将数字转换为整数，并压入操作数栈。
   • 操作符: 与操作符栈顶元素比较优先级，如果当前操作符优先级小于等于栈顶操作符，则弹出栈顶操作符和两个操作数，进行计算，并将结果压入操作数栈，然后再将当前操作符压入操作符栈。
   • 其他字符: 忽略。
3. 计算最终结果: 表达式扫描完毕后，弹出操作符栈中所有操作符，并进行计算，最终操作数栈中剩余的值即为表达式的结果。

该代码实现了基本的算术运算，并能处理括号，使用LR分析法和语法制导翻译法，方便理解和扩展。