C语言中栈和队列实现表达式求值的实例

在 C 语言中，可以利用栈和队列来实现表达式求值。表达式求值是将字符串形式的表达式转换成计算结果的过程，包括算数表达式和逻辑表达式两种类型。下面将分别对这两种表达式求值进行实例说明。

算数表达式求值

算数表达式求值的过程包括词法分析、语法分析和计算三个过程。词法分析是将字符串表达式拆分成由数字、运算符和括号等组成的多个 Token，语法分析是按照优先级和括号顺序逐步计算拆分后的 Token，计算是最终得到计算结果的过程。

以下是一个简单的算数表达式求值的例子：

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

#define MAX_EXPR_SIZE 100

typedef struct {
    char expr[MAX_EXPR_SIZE];
    int len;
} Expr;

typedef struct {
    int num;
    char op;
} Token;

typedef struct {
    int num[MAX_EXPR_SIZE];
    int top;
} Stack;

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

void push(Stack *stack, int num) {
    stack->top++;
    stack->num[stack->top] = num;
}

int pop(Stack *stack) {
    int num = stack->num[stack->top];
    stack->top--;
    return num;
}

int calculate(Token token, int num1, int num2) {
    switch (token.op) {
        case '+':
            return num1 + num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
        case '/':
            return num1 / num2;
        default:
            return 0;
    }
}

int eval(Expr expr) {
    Stack num_stack;
    num_stack.top = -1;
    int num1, num2;
    char op;
    Token token;
    for (int i = 0; i < expr.len; i++) {
        if (isdigit(expr.expr[i])) {
            int num = expr.expr[i] - '0';
            i++;
            while (i < expr.len && isdigit(expr.expr[i])) {
                num = num * 10 + expr.expr[i] - '0';
                i++;
            }
            push(&num_stack, num);
            i--;
        } else if (expr.expr[i] == ')') {
            num2 = pop(&num_stack);
            op = pop(&num_stack);
            num1 = pop(&num_stack);
            push(&num_stack, calculate((Token){op}, num1, num2));
        } else if (expr.expr[i] == '+' || expr.expr[i] == '-' || expr.expr[i] == '*' || expr.expr[i] == '/') {
            while (num_stack.top >= 0 && op_priority(num_stack.num[num_stack.top]) >= op_priority(expr.expr[i])) {
                num2 = pop(&num_stack);
                op = pop(&num_stack);
                num1 = pop(&num_stack);
                push(&num_stack, calculate((Token){op}, num1, num2));
            }
            push(&num_stack, expr.expr[i]);
        } else if (expr.expr[i] == '(') {
            push(&num_stack, expr.expr[i]);
        }
    }
    while (num_stack.top >= 0) {
        num2 = pop(&num_stack);
        op = pop(&num_stack);
        num1 = pop(&num_stack);
        push(&num_stack, calculate((Token){op}, num1, num2));
    }
    return pop(&num_stack);
}

int main() {
    Expr expr = {"(5+1)*6/2-3"};
    expr.len = strlen(expr.expr);
    printf("Result: %d\n", eval(expr));
    return 0;
}

逻辑表达式求值

逻辑表达式求值的过程相对比较简单，只需要根据布尔运算的规则逐个计算即可。逻辑表达式求值的结果只有 true 或 false 两种。

以下是一个简单的逻辑表达式求值的例子：

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

#define MAX_EXPR_SIZE 100

typedef struct {
    char expr[MAX_EXPR_SIZE];
    int len;
} Expr;

typedef struct {
    char op;
} Token;

typedef struct {
    int value[MAX_EXPR_SIZE];
    int top;
} Stack;

void push(Stack *stack, int value) {
    stack->top++;
    stack->value[stack->top] = value;
}

int pop(Stack *stack) {
    int num = stack->value[stack->top];
    stack->top--;
    return num;
}

int eval(Expr expr) {
    Stack value_stack;
    value_stack.top = -1;
    int value1, value2;
    char op;
    Token token;
    for (int i = 0; i < expr.len; i++) {
        if (expr.expr[i] == 't') {
            push(&value_stack, 1);
        } else if (expr.expr[i] == 'f') {
            push(&value_stack, 0);
        } else if (expr.expr[i] == '|') {
            value2 = pop(&value_stack);
            value1 = pop(&value_stack);
            push(&value_stack, value1 || value2);
        } else if (expr.expr[i] == '&') {
            value2 = pop(&value_stack);
            value1 = pop(&value_stack);
            push(&value_stack, value1 && value2);
        } else if (expr.expr[i] == '!') {
            value1 = pop(&value_stack);
            push(&value_stack, !value1);
        }
    }
    return pop(&value_stack);
}

int main() {
    Expr expr = {"(t|f)&!f"};
    expr.len = strlen(expr.expr);
    printf("Result: %d\n", eval(expr));
    return 0;
}

以上为根据栈和队列实现的算数表达式和逻辑表达式求值的两个例子。当然，这两个例子只是简单的示例，在实际的应用中还需要考虑更完善的错误处理机制、数据结构设计等问题。