数据结构 第三章 栈和队列 练习题3.2.5 表达式求值 C语言代码

本代码没有处理某个数字为负数的情况,感兴趣的小伙伴可以分享自己的思路和代码

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

#define MAX_SIZE 100

int numStk[MAX_SIZE], num_hh = 0;
char opStk[MAX_SIZE], op_hh = 0;

// (1)Stack creation and initialization
/* -------------------------------- 数栈和符号栈begin  -------------------------------- */

/**
 * Push a number onto the number stack
 * @param num The number to push
 */
void pushNum(int num) {
    numStk[++num_hh] = num;
}

/**
 * Pop a number from the number stack
 * @return The popped number
 */
int popNum() {
    return numStk[num_hh--];
}
/**
 * @return The top element of the number stack
 */
int topNum() {
    return numStk[num_hh];
}

/**
 * Push an operator onto the operator stack
 * @param op The operator to push
 */
void pushOp(char op) {
    opStk[++op_hh] = op;
}

/**
 * Pop an operator from the operator stack
 * @return The popped operator
 */
char popOp() {
    return opStk[op_hh--];
}
/**
 * @return the number of operator stacks
 */
int opStkSize()
{
    return op_hh;
}


/* -------------------------------- 数栈和符号栈end  -------------------------------- */


// (2)Operator priority and calculation
/* -------------------------------- 计算器和优先级比较begin  -------------------------------- */
int calc(int a, int b, char op)
{
    switch (op)
    {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            if (b == 0)
            {
                perror("The divisor cannot be 0");
                exit(1);
            }
            return a / b;
        default:
            printf("c = %c",op);
            perror("Invalid operator");
            exit(1);
    }
}

int precedence(char op)
{
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// 把符号栈全部取出和数栈进行计算
void calcSameLevel()
{
    while (opStkSize())
    {
        // 出栈计算
        int b = popNum();
        int a = popNum();
        char op = popOp();
        // 把运算结果入栈
        int tmp = calc(a,b,op);
        pushNum(tmp);
    }
}
/* -------------------------------- 计算器和优先级比较end  -------------------------------- */

//(3)Function for calculating expressions
/* -------------------------------- 控制数据提取和计算时机begin  -------------------------------- */
/*
 * 出栈和入栈的判定
 * 前一个符号 < 新增符号 入栈
 * 前一个符号  >= 新增符号 取出栈顶计算
 */
int infixToPostfixEval(char *exp)
{
    // 处理多位数
    int num = 0;

    int pre = 0;// 0表示上一个是符号 1表示上一个是数字
    char preOP = ' ';// 保留前一个符号

    for (int i = 0; exp[i]; ++i)
    {
        char c = exp[i];

        // 处理数字
        if (isdigit(c))
        {
            // 多位数
            if(pre)
            {
                int tmp = num * 10 + (c-'0');
                // 更新栈顶
                popNum();//出栈
                pushNum(tmp);//入栈
                num = topNum();
            }
                // 新增
            else
            {
                int tmp = c - '0';
                pushNum(tmp);
                num = topNum();
            }
            pre = 1;
        }
        else if(c == '(')
        {
            // 入符号栈
            opStk[++op_hh] = c;
            pre = 0;
            // 更新preOP
            preOP = c;
        }
        else if(c == ')')
        {
            // 遇到右括号，则计算栈内直到左括号的所有运算符
            while (op_hh && opStk[op_hh] != '(')
            {
                int b = numStk[num_hh--];
                int a = numStk[num_hh--];
                char op = opStk[op_hh--];
                numStk[++num_hh] = calc(a, b, op);
            }
            // 弹出左括号（不参与计算）
            if (op_hh) op_hh--;
            // 更新preOP
            preOP = c;
            pre = 0; // 重置状态
            num = 0; // 重置数字
        }
        else
        {
            // 比较运算符优先级
            if(precedence(preOP) < precedence(c))
            {
                // 入栈
                opStk[++op_hh] = c;
            }
            else
            {
                //例: 2*2/4+3 preOP = '/' c = '+'
                calcSameLevel();
                // 新符号入栈
                opStk[++op_hh] = c;
            }
            // 更新pre状态
            pre = 0;
            // 更新preOP
            preOP = c;
            // 更新num
            num = 0;
        }
    }
    calcSameLevel();
    return popNum();
}

/* -------------------------------- 控制数据提取和计算时机end  -------------------------------- */
int main()
{
    // test :(2*3)+(100+(41*2))*((3*3)-(8/2))
    char expression[MAX_SIZE];
    printf("请输入一组正整数构成的表达式:\n");
    scanf("%s", expression);

    int res = infixToPostfixEval(expression);
    printf("%s = %d",expression,res);
    return 0;
}

原文地址：https://blog.csdn.net/qq_63561301/article/details/142439775

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！