算术表达式求值的算法C语言程序

以下是一个简单的算术表达式求值的算法C语言程序：

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

#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    double items[MAX_STACK_SIZE];
} Stack;

void push(Stack *s, double value) {
    if (s->top == MAX_STACK_SIZE - 1) {
        printf("Stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    s->items[++(s->top)] = value;
}

double pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return s->items[(s->top)--];
}

int is_operator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

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

double evaluate(char *expression) {
    Stack operand_stack;
    operand_stack.top = -1;

    Stack operator_stack;
    operator_stack.top = -1;

    int i = 0;
    while (expression[i] != '\0') {
        if (expression[i] >= '0' && expression[i] <= '9') {
            double value = 0.0;
            while (expression[i] >= '0' && expression[i] <= '9') {
                value = value * 10.0 + (double)(expression[i] - '0');
                i++;
            }
            if (expression[i] == '.') {
                double factor = 1.0;
                i++;
                while (expression[i] >= '0' && expression[i] <= '9') {
                    factor /= 10.0;
                    value = value + (double)(expression[i] - '0') * factor;
                    i++;
                }
            }
            push(&operand_stack, value);
        } else if (is_operator(expression[i])) {
            while (operator_stack.top != -1 && precedence(expression[i]) <= precedence((char)operator_stack.items[operator_stack.top])) {
                double operand2 = pop(&operand_stack);
                double operand1 = pop(&operand_stack);
                char operator = (char)pop(&operator_stack);
                switch (operator) {
                    case '+':
                        push(&operand_stack, operand1 + operand2);
                        break;
                    case '-':
                        push(&operand_stack, operand1 - operand2);
                        break;
                    case '*':
                        push(&operand_stack, operand1 * operand2);
                        break;
                    case '/':
                        if (operand2 == 0.0) {
                            printf("Division by zero!\n");
                            exit(EXIT_FAILURE);
                        }
                        push(&operand_stack, operand1 / operand2);
                        break;
                }
            }
            push(&operator_stack, (double)expression[i]);
            i++;
        } else {
            printf("Invalid character: %c\n", expression[i]);
            exit(EXIT_FAILURE);
        }
    }

    while (operator_stack.top != -1) {
        double operand2 = pop(&operand_stack);
        double operand1 = pop(&operand_stack);
        char operator = (char)pop(&operator_stack);
        switch (operator) {
            case '+':
                push(&operand_stack, operand1 + operand2);
                break;
            case '-':
                push(&operand_stack, operand1 - operand2);
                break;
            case '*':
                push(&operand_stack, operand1 * operand2);
                break;
            case '/':
                if (operand2 == 0.0) {
                    printf("Division by zero!\n");
                    exit(EXIT_FAILURE);
                }
                push(&operand_stack, operand1 / operand2);
                break;
        }
    }

    return pop(&operand_stack);
}

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

该程序使用两个栈：一个操作数栈和一个操作符栈。它通过遍历输入的表达式来逐步构建操作数栈和操作符栈，并在需要时执行相应的操作。在遍历完整个表达式后，它把操作符栈中剩余的操作符依次弹出，按顺序应用到操作数栈中的操作数上，最终得到表达式的值。