数据结构表达式求值c

表达式求值是计算机科学中的一个重要问题。在C语言中，可以使用栈来实现表达式求值。下面是一个使用栈实现的表达式求值的示例代码：

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

#define MAX_SIZE 100

// 定义操作符栈和操作数栈
char operator_stack[MAX_SIZE];
int operand_stack[MAX_SIZE];

int top_operator = -1;
int top_operand = -1;

// 操作符栈的入栈操作
void push_operator(char op) {
    if (top_operator == MAX_SIZE - 1) {
        printf("Operator stack is full!\n");
        exit(1);
    }
    operator_stack[++top_operator] = op;
}

// 操作符栈的出栈操作
char pop_operator() {
    if (top_operator == -1) {
        printf("Operator stack is empty!\n");
        exit(1);
    }
    return operator_stack[top_operator--];
}

// 操作数栈的入栈操作
void push_operand(int num) {
    if (top_operand == MAX_SIZE - 1) {
        printf("Operand stack is full!\n");
        exit(1);
    }
    operand_stack[++top_operand] = num;
}

// 操作数栈的出栈操作
int pop_operand() {
    if (top_operand == -1) {
        printf("Operand stack is empty!\n");
        exit(1);
    }
    return operand_stack[top_operand--];
}

// 判断是否为操作符
int is_operator(char op) {
    return (op == '+' || op == '-' || op == '*' || op == '/');
}

// 获取操作符优先级
int get_precedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    }
    if (op == '*' || op == '/') {
        return 2;
    }
    return 0;
}

// 计算表达式的值
int evaluate_expression(char* expression) {
    int i = 0;
    while (expression[i] != '\0') {
        // 如果是空格，则直接忽略
        if (expression[i] == ' ') {
            i++;
            continue;
        }
        // 如果是数字，则将连续的数字字符转换为对应的整数值，并入栈
        else if (isdigit(expression[i])) {
            int num = 0;
            while (isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            push_operand(num);
        }
        // 如果是操作符
        else if (is_operator(expression[i])) {
            // 如果操作符栈为空，则直接入栈
            if (top_operator == -1) {
                push_operator(expression[i]);
            }
            // 如果操作符栈不为空，比较操作符优先级
            else {
                char top_op = operator_stack[top_operator];
                // 当前操作符优先级小于等于栈顶操作符优先级，则弹出栈顶操作符和两个操作数进行运算，将结果入栈
                if (get_precedence(expression[i]) <= get_precedence(top_op)) {
                    int operand2 = pop_operand();
                    int operand1 = pop_operand();
                    switch (top_op) {
                        case '+':
                            push_operand(operand1 + operand2);
                            break;
                        case '-':
                            push_operand(operand1 - operand2);
                            break;
                        case '*':
                            push_operand(operand1 * operand2);
                            break;
                        case '/':
                            push_operand(operand1 / operand2);
                            break;
                    }
                    pop_operator();
                    // 继续比较当前操作符与新的栈顶操作符的优先级
                    continue;
                }
                // 当前操作符优先级大于栈顶操作符优先级，则直接入栈
                else {
                    push_operator(expression[i]);
                }
            }
        }
        // 如果是左括号，直接入栈
        else if (expression[i] == '(') {
            push_operator(expression[i]);
        }
        // 如果是右括号，则依次弹出操作符栈的操作符和操作数栈的操作数进行运算，直到遇到左括号
        else if (expression[i] == ')') {
            while (operator_stack[top_operator] != '(') {
                char op = pop_operator();
                int operand2 = pop_operand();
                int operand1 = pop_operand();
                switch (op) {
                    case '+':
                        push_operand(operand1 + operand2);
                        break;
                    case '-':
                        push_operand(operand1 - operand2);
                        break;
                    case '*':
                        push_operand(operand1 * operand2);
                        break;
                    case '/':
                        push_operand(operand1 / operand2);
                        break;
                }
            }
            pop_operator(); // 弹出左括号
        }
        i++;
    }
    // 当表达式遍历完成后，如果操作符栈不为空，则依次弹出操作符栈的操作符和操作数栈的操作数进行运算
    while (top_operator != -1) {
        char op = pop_operator();
        int operand2 = pop_operand();
        int operand1 = pop_operand();
        switch (op) {
            case '+':
                push_operand(operand1 + operand2);
                break;
            case '-':
                push_operand(operand1 - operand2);
                break;
            case '*':
                push_operand(operand1 * operand2);
                break;
            case '/':
                push_operand(operand1 / operand2);
                break;
        }
    }
    // 返回操作数栈的栈顶元素，即为表达式的值
    return operand_stack[top_operand];
}

int main() {
    char expression[] = "3 + 4 * 2 - ( 1 + 2 )";

    int result = evaluate_expression(expression);

    printf("The result is: %d\n", result);

    return 0;
}

这段代码可以计算包含加减乘除和括号的表达式的值。它按照算术运算符的优先级进行计算，并使用栈来保存操作符和操作数。运算符栈用于判断运算符的优先级，操作数栈用于保存操作数和计算结果。