用程序实现求解用户输入的表达式的值，例如输入1+2*3-16/2，则输出为-1。数据结构C语言

在C语言中，实现一个能够计算用户输入表达式值的程序通常需要用到递归解析算法和栈（stack）。你可以使用栈来存储运算符和操作数，通过遍历用户输入的字符串，并根据运算符优先级规则来进行计算。

首先，定义一个函数`evalExpression`接收用户输入的字符串作为参数：

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

#define MAX_TOKENS 100
#define MAX_TOKEN_LEN 50

typedef struct {
    char op; // 运算符
    double num; // 数字
} Token;

Token tokens[MAX_TOKENS];
int token_count = 0;

double applyOp(double left, char op, double right) {
    switch (op) {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            if (right != 0)
                return left / right;
            else
                return INFINITY; // 避免除数为零的错误
        default:
            printf("Invalid operator\n");
            exit(EXIT_FAILURE);
    }
}

void tokenize(char* expression) {
    char* token = strtok(expression, " ()");
    while (token != NULL) {
        if (isdigit(*token)) { // 如果是数字
            double num = atof(token); // 转换为浮点数
            tokens[token_count].num = num;
        } else { // 如果是运算符
            tokens[token_count].op = *token;
        }
        token = strtok(NULL, " ()"); // 获取下一个分隔符
        token_count++;
    }
}

double evalExpression(char* expression) {
    if (token_count == 0) {
        printf("Empty expression or invalid format\n");
        return 0;
    }

    stack(Token*) s = malloc(sizeof(stack(Token*)));
    s->top = NULL;

    for (int i = 0; i < token_count; i++) {
        if (isdigit(tokens[i].num)) {
            push(s, &tokens[i]); // 先入栈数字
        } else {
            while (s->top != NULL && isOperator(s->top->op, tokens[i].op)) {
                pop(s); // 出栈并应用运算符
            }
            push(s, &tokens[i]); // 再入栈运算符
        }
    }

    while (s->top != NULL) {
        Token* top = pop(s);
        if (isdigit(top->num)) { // 没有运算符，直接出栈数字并返回结果
            double result = top->num;
            while (s->top != NULL && isOperator(s->top->op, '+')) {
                top = pop(s);
                result += top->num;
            }
            return result;
        } else {
            double left = pop(s)->num;
            double right = pop(s)->num;
            double result = applyOp(left, top->op, right);
            free(top);
            top = malloc(sizeof(Token));
            top->num = result;
            push(s, top);
        }
    }

    return s->top->num; // 应该不会到达这里，但如果程序意外终止，返回最后一个计算的结果
}

// 辅助函数判断是否为左结合运算符
bool isLeftAssoc(char op1, char op2) {
    return op1 == '(' || (op2 == '+' || op2 == '-') && op1 == '*' || op1 == '/';
}

// 辅助函数判断是否为同一运算符集
bool isOperator(char op1, char op2) {
    return op1 == op2 || (isLeftAssoc(op1, op2) && op1 == '/');
}

// 栈操作
void push(stack(Token*) s, Token* token) {
    if (s->top == NULL) {
        s->top = token;
    } else {
        Token* new_top = (Token*)malloc(sizeof(Token));
        *new_top = *s->top;
        s->top = new_top;
        s->top->next = token;
    }
}

Token* pop(stack(Token*) s) {
    Token* temp = s->top;
    if (s->top == NULL) {
        return NULL;
    }
    s->top = s->top->next;
    if (s->top == NULL) {
        free(temp);
    }
    return temp;
}

int main() {
    char expression[100];
    printf("Enter an expression to evaluate: ");
    fgets(expression, sizeof(expression), stdin);

    expression[strlen(expression) - 1] = '\0'; // 去除fgets获取的最后一行的换行符

    double result = evalExpression(expression);
    printf("Result: %.2lf\n", result);

    return 0;
}