栈在表达式求值的c语言代码实现

很好的问题！栈在C语言表达式求值中扮演着非常重要的角色。具体实现可以使用两个栈，一个用于存储操作符和左括号，另一个用于存储操作数。对于每个读入的符号，我们根据优先级和括号来处理：

1. 如果是数字，直接入操作数栈。

2. 如果是左括号，直接入操作符栈。

3. 如果是右括号，将操作符栈中的符号依次出栈，并将对应的操作数出栈，直到遇到左括号为止。将操作符和操作数进行计算，并将结果入操作数栈。左括号出栈丢弃。

4. 如果是操作符，与操作符栈栈顶元素进行比较，如果优先级高于或同级，则将操作符和操作数分别入栈。如果优先级低于栈顶操作符，则将栈顶操作符出栈并取出相应的操作数进行运算，再将结果入操作数栈。重复此操作直到栈顶符号的优先级低于当前符号。

最后，当所有符号读入之后，操作符栈中可能还剩下操作符，按照以上方法进行处理直到操作符栈为空。最后，操作数栈中剩下的元素即为表达式的值。

希望我的回答能够帮到你！

相关问题

利用栈实现表达式求值C语言版

好的，以下是一个简单的栈实现表达式求值的C语言代码：

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

#define STACK_SIZE 100

// 定义栈结构体
typedef struct {
    int top;
    int data[STACK_SIZE];
} Stack;

// 初始化栈
void init(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int is_empty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int is_full(Stack *s) {
    return s->top == STACK_SIZE - 1;
}

// 入栈
void push(Stack *s, int x) {
    if (is_full(s)) {
        printf("Stack overflow!\n");
        exit(1);
    }
    s->top++;
    s->data[s->top] = x;
}

// 出栈
int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow!\n");
        exit(1);
    }
    int x = s->data[s->top];
    s->top--;
    return x;
}

// 获取栈顶元素
int peek(Stack *s) {
    if (is_empty(s)) {
        printf("Stack empty!\n");
        exit(1);
    }
    return s->data[s->top];
}

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

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

// 表达式求值
int evaluate(char *expr) {
    Stack num_stack, op_stack;
    init(&num_stack);
    init(&op_stack);
    int len = strlen(expr);
    for (int i = 0; i < len; i++) {
        if (isspace(expr[i])) {
            continue;
        } else if (isdigit(expr[i])) {
            int num = 0;
            while (i < len && isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;
            push(&num_stack, num);
        } else if (is_operator(expr[i])) {
            while (!is_empty(&op_stack) && precedence(peek(&op_stack)) >= precedence(expr[i])) {
                int num2 = pop(&num_stack);
                int num1 = pop(&num_stack);
                char op = pop(&op_stack);
                switch (op) {
                case '+':
                    push(&num_stack, num1 + num2);
                    break;
                case '-':
                    push(&num_stack, num1 - num2);
                    break;
                case '*':
                    push(&num_stack, num1 * num2);
                    break;
                case '/':
                    push(&num_stack, num1 / num2);
                    break;
                }
            }
            push(&op_stack, expr[i]);
        } else {
            printf("Invalid character: %c\n", expr[i]);
            exit(1);
        }
    }
    while (!is_empty(&op_stack)) {
        int num2 = pop(&num_stack);
        int num1 = pop(&num_stack);
        char op = pop(&op_stack);
        switch (op) {
        case '+':
            push(&num_stack, num1 + num2);
            break;
        case '-':
            push(&num_stack, num1 - num2);
            break;
        case '*':
            push(&num_stack, num1 * num2);
            break;
        case '/':
            push(&num_stack, num1 / num2);
            break;
        }
    }
    return pop(&num_stack);
}

// 测试
int main() {
    char expr[100];
    printf("Enter an expression: ");
    fgets(expr, 100, stdin);
    printf("Result: %d\n", evaluate(expr));
    return 0;
}

该代码主要利用了两个栈来实现表达式求值，一个栈用来存储操作数，另一个栈用来存储操作符。遍历表达式字符串，如果遇到数字字符，则将其转换为整数并入操作数栈；如果遇到操作符，则与操作符栈顶元素比较优先级，如果当前操作符优先级较低，则将操作符栈顶元素弹出并将操作数栈顶的两个元素进行计算，结果再入操作数栈。最后，将操作符栈中的剩余操作符依次弹出并进行计算，直到操作符栈为空，最后操作数栈中剩余的元素即为表达式的值。

用栈编写表达式求值C语言

好的，我可以为您介绍一下用栈来实现表达式求值的C语言代码。

首先，我们需要定义一个栈结构体，用来存储操作符和操作数。例如：

typedef struct {
    int top;
    int data[100];
} Stack;

接下来，我们需要实现栈的基本操作，包括入栈、出栈、判断栈是否为空等操作。例如：

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

int pop(Stack *s) {
    return s->data[s->top--];
}

int is_empty(Stack *s) {
    return s->top == -1;
}

有了栈的基本操作，我们就可以开始实现表达式求值了。具体步骤如下：

1. 初始化一个空栈。
2. 从左到右遍历表达式中的每一个字符，如果是数字，则将其转换为整数并入栈。
3. 如果是操作符，则从栈中弹出两个数，进行计算，并将计算结果入栈。
4. 最后栈中只剩下一个数，即为表达式的计算结果。

下面是用栈实现表达式求值的C语言代码：

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

typedef struct {
    int top;
    int data[100];
} Stack;

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

int pop(Stack *s) {
    return s->data[s->top--];
}

int is_empty(Stack *s) {
    return s->top == -1;
}

int calculate(int a, int b, char op) {
    switch(op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}

int evaluate(char *expr) {
    Stack s;
    s.top = -1;
    int i, a, b;
    char op;
    for (i = 0; expr[i] != '\0'; i++) {
        if (expr[i] >= '0' && expr[i] <= '9') {
            push(&s, expr[i] - '0');
        } else {
            b = pop(&s);
            a = pop(&s);
            op = expr[i];
            push(&s, calculate(a, b, op));
        }
    }
    return pop(&s);
}

int main() {
    char expr[100];
    printf("请输入表达式：");
    scanf("%s", expr);
    printf("%s = %d\n", expr, evaluate(expr));
    return 0;
}

希望这段代码能够帮助到您，有任何问题请随时提出。