算术表达式求解数据结构 c语言实现代码

在C语言中，解析和求解算术表达式通常会涉及到递归下降解析法（Recursive Descent Parsing）或栈的操作，比如使用中缀表达式转换为后缀表达式（Reverse Polish Notation, RPN），然后计算RPN序列。这里是一个简单的例子，展示如何使用栈来实现中缀转后缀（也称为逆波兰表示法）的过程：

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

typedef enum {NUMBER, LEFT_PAREN, RIGHT_PAREN, PLUS, MINUS, MUL, DIV} token_type;

char* tokens[] = {"+", "-", "*", "/", "(", ")"};
int precedence[4] = {0, 0, 1, 2};

// 函数定义
void push(int value, stack_t *s);
double pop(stack_t *s);
double evaluate_postfix(char *tokens, int n);

// 结构体定义
typedef struct {
    double num;
    char op;
    int priority;
} item;

stack_t {
    item items[50];
    int top;
};

// 辅助函数
void push(int value, stack_t *s) {
    if (s->top == 50) {
        printf("Stack overflow!\n");
        return;
    }
    s->items[s->top++] = (item){value, '\0', 0};
}

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

// 主函数
double evaluate_expression(char *expression) {
    stack_t s = {0};
    char *token = strtok(expression, " ()");
    while (token != NULL) {
        for (int i = 0; i < sizeof(tokens) / sizeof(tokens[0]); ++i) {
            if (strcmp(token, tokens[i]) == 0) {
                if (token[0] == '(') {
                    push(i, &s);
                } else if (token[0] == ')') {
                    while (pop(&s) != '(') {} // 丢弃左括号直到遇到第一个左括号
                } else {
                    while (s.top > 0 && precedence[s.items[s.top - 1].priority] >= precedence[i]) {
                        push(evaluate_postfix(s.items, s.top), &s);
                        s.top--;
                    }
                    push(i, &s);
                }
                break;
            }
        }
        token = strtok(NULL, " ()");
    }

    while (s.top > 0) {
        push(evaluate_postfix(s.items, s.top), &s);
        s.top--;
    }

    return pop(&s);
}

// 后缀表达式的计算
double evaluate_postfix(char *tokens, int n) {
    stack_t s = {0};
    for (int i = 0; i < n; ++i) {
        if (isdigit(tokens[i])) {
            push(atof(tokens[i]), &s);
        } else {
            double b = pop(&s);
            double a = pop(&s);
            switch (tokens[i]) {
                case '+': push(a + b, &s); break;
                case '-': push(a - b, &s); break;
                case '*': push(a * b, &s); break;
                case '/': push(a / b, &s); break;
            }
        }
    }
    return pop(&s);
}

int main() {
    char expression[] = "(2+3)*4-5";
    printf("Result: %.2f\n", evaluate_expression(expression));
    return 0;
}

这个代码首先将输入的算术表达式按照运算符的优先级和括号规则划分成后缀形式，然后计算得到结果。注意这只是一个基础示例，实际的实现可能会更复杂，包括处理错误边界、优化算法等。