c语言怎么用栈实现表达式求值

   2025-02-13 3630
核心提示:使用栈实现表达式求值的一般方法如下:1.定义两个栈,一个用于存储操作数,另一个用于存储操作符。2.遍历表达式中的每个字符,按

使用栈实现表达式求值的一般方法如下:

1.定义两个栈,一个用于存储操作数,另一个用于存储操作符。

2.遍历表达式中的每个字符,按照以下规则处理:

如果字符是操作数,则将其转换为整数,并将其压入操作数栈中。

如果字符是操作符,则按照以下步骤处理:

如果操作符栈为空,或者操作符栈的栈顶操作符为左括号’(',则将操作符压入操作符栈中。如果操作符栈不为空,并且栈顶操作符的优先级大于等于当前操作符的优先级,则从操作数栈中弹出两个操作数,从操作符栈中弹出一个操作符,进行计算并将结果压入操作数栈中,重复该步骤直到操作符栈为空,或者栈顶操作符的优先级小于当前操作符的优先级,然后将当前操作符压入操作符栈中。如果当前操作符为右括号’)‘,则从操作数栈中弹出两个操作数,从操作符栈中弹出一个操作符,进行计算并将结果压入操作数栈中,重复该步骤直到遇到左括号’(',然后将左括号从操作符栈中弹出。

3.遍历完整个表达式后,检查操作符栈是否为空,如果不为空,则从操作数栈中弹出两个操作数,从操作符栈中弹出一个操作符,进行计算并将结果压入操作数栈中,直到操作符栈为空。

4.最后,操作数栈中剩下的唯一一个元素就是表达式的最终结果。

以下是一个使用栈实现表达式求值的示例代码:

#include <stdio.h>#include <stdlib.h>#include <ctype.h>#define MAX_SIZE 100// 定义栈结构typedef struct {    int data[MAX_SIZE];    int top;} Stack;// 初始化栈void initStack(Stack* s) {    s->top = -1;}// 判断栈是否为空int isEmpty(Stack* s) {    return s->top == -1;}// 判断栈是否已满int isFull(Stack* s) {    return s->top == MAX_SIZE - 1;}// 元素入栈void push(Stack* s, int val) {    if (isFull(s)) {        printf("Stack is full!\n");        return;    }    s->data[++s->top] = val;}// 元素出栈int pop(Stack* s) {    if (isEmpty(s)) {        printf("Stack is empty!\n");        return -1;    }    return s->data[s->top--];}// 获取栈顶元素int top(Stack* s) {    if (isEmpty(s)) {        printf("Stack is empty!\n");        return -1;    }    return s->data[s->top];}// 获取操作符的优先级int getPriority(char op) {    switch (op) {        case '+':        case '-':            return 1;        case '*':        case '/':            return 2;        default:            return 0;    }}// 执行计算int calculate(int num1, int num2, char op) {    switch (op) {        case '+':            return num1 + num2;        case '-':            return num1 - num2;        case '*':            return num1 * num2;        case '/':            return num1 / num2;        default:            return 0;    }}// 使用栈求解表达式的值int evaluateExpression(char* expression) {    Stack numStack; // 操作数栈    Stack opStack;  // 操作符栈    initStack(&numStack);    initStack(&opStack);        int num = 0; // 用于处理多位数    int sign = 1; // 用于处理负数

 
 
更多>同类维修知识
推荐图文
推荐维修知识
点击排行
网站首页  |  关于我们  |  联系方式  |  用户协议  |  隐私政策  |  网站留言