如何利用栈实现表达式求值

前言

假如要你实现一个可以识别表达式的简易计算器,你会怎么实现?例如用户输入:

3 + 5 * (2 - 4)

可以直接得出计算结果:-7。对于人类来说,我们很容易计算出来,因为我们从左往右看,看到后面括号时,知道括号内的计算优先级最高,因此可以先计算括号内的,然后反过来计算乘法,最后计算加法,得到最终结果。

后缀表达式

而对于计算机来说,实际也可以采用类似的顺序,先记录存储3为a,然后存储5为b,计算2-4结果存入c,再然后计算b*c存储d,最终计算a+d得到最终结果。而这种计算过程的操作顺序可描述如下(把操作符号放在操作数后面):

3 5 2 4 - * +

这种记法叫做后缀或逆波兰记法(而我们平常见到的叫中缀记法),它的特点是不需要用括号就能表示出整个表达式哪部分运算先进行,也就是说不需要考虑优先级,这非常符合计算机的处理方式。这种记法很容易使用我们前面介绍的栈来求值,但是前提是需要将中缀表达式先转换为后缀表达式。对于这种转换,我们也可以使用前面介绍的《栈-C语言实现》或者将要介绍的树来完成,因篇幅有限,本文不准备介绍。

接下来将会介绍如何利用中缀表达式进行求值。

利用栈实现中缀表达式求值

前面也说到,所谓中缀表达式,就是我们能看到的正常表达式,中缀表达式求值,也就是直接对输入的表达式进行求值。为简单起见,我们这里假设只涉及加减乘除和小括号,并且操作数都是正整数,不涉及更加复杂的数据或运算。

计算思路:

  • 使用两个栈,stack0用于存储操作数,stack1用于存储操作符
  • 从左往右扫描,遇到操作数入栈stack0
  • 遇到操作符时,如果优先级低于或等于栈顶操作符优先级,则从stack0弹出两个元素进行计算,并压入stack0,继续与栈顶操作符的比较优先级
  • 如果遇到操作符高于栈顶操作符优先级,则直接入栈stack1
  • 遇到左括号,直接入栈stack1,遇到右括号,则直接出栈并计算,直到遇到左括号

上面的思路可能看起来不是很明确,我们举一个简单的例子,假如要对下面的表达式求值:

6 * (2 + 3 )* 8 + 5

我们从左往右开始扫描。首先遇到操作数‘6’,和操作符‘*’,分别入栈 stack0:

栈顶

6

stack1:

栈顶

*

继续往后扫描,遇到‘(’直接入栈,‘2’入栈,栈顶是左括号,’+‘入栈,‘3’入栈 stack0:

栈顶

6

2

3

stack1:

栈顶

*

(

+

继续往后扫描,遇到右括号,它与栈顶操作符‘+’相比,优先级要高,因此,将‘+’出栈,弹出两个操作数‘3’,‘2’,计算结果得到‘5’,并入栈:

stack0:

栈顶

6

5

stack1:

栈顶

*

(

继续出栈,直到遇到左括号 stack0:

栈顶

6

5

stack1:

栈顶

*

继续往后扫描,遇到操作符‘’,优先级与栈顶‘’优先级相同,因此弹出操作数并计算得到30入栈,最后‘*’入栈

stack0:

栈顶

30

stack1:

栈顶

*

继续扫描,‘8’入栈,操作符‘+’优先级小于‘*’,弹出操作数计算得到结果‘240’,并将其入栈,最后‘+’也入栈

stack0:

栈顶

240

stack1:

栈顶

+

最后‘5’入栈,发现操作符栈不为空,弹出操作符‘+’和两个操作数,并进行计算,得到‘245’,入栈,得到最终结果。

stack0:

栈顶

245

stack1:

代码实现

以下为关键部分代码,完整可运行代码可阅读原文进行查看或访问 https://www.yanbinghu.com/2019/03/24/57779.html

/*用于记录符号的优先级,这里浪费了一些内存,可以优化*/
static char priority[128] = {0};
void priorityInit()
{
    /*初始化优先级,值越小,优先级越高*/
    priority['+'] = 4;
    priority['-'] = 4;
    priority['*'] = 3;
    priority['/'] = 3;
    priority['('] = 1;
    priority[')'] = 1;


}
/*比较运算符的优先级,op1优先级大于op2时,返回大于0的值*/
int priorityCompare(char op1,char op2)
{
    return priority[op2] - priority[op1];
}
/*出栈操作符和操作数进行计算*/
int calcOp(StackInfo_st *nums,StackInfo_st *ops,int nowOp)
{
    int a ,b,op;
    stack_pop(ops,&op);
    printf("op %c is <= %c\n",nowOp,op);
    printf("get op from stack %c\n",op);
    if(SUCCESS != stack_pop(nums,&b))
    {
        printf("pop failed\n");
        return -1;
    }
    if(SUCCESS != stack_pop(nums,&a))
    {
        printf("pop failed\n");
        return 0;
    }
    printf("get b from stack %d\n",b);

    printf("get a from stack %d\n",a);
    switch(op)
    {
        case '+':
        {
            printf("push %d into stack\n",a+b);
            stack_push(nums,a+b);
            break;
        }
        case '-':
        {
            stack_push(nums,a-b);
            break;
        }
        case '*':
        {
            printf("push %d into stack\n",a*b);
            stack_push(nums,a*b);
            break;
        }
        case '/':
        {
            printf("push %d into stack\n",a/b);
            stack_push(nums,a/b);
            break;
        }
    }
    return 1;
}
int calc(const char* exp,int *result)
{
    if(NULL == exp || NULL == result)
        return FAILURE;
    /*创建栈,用于保存数*/
    StackInfo_st nums;
    nums.topOfStack = TOP_OF_STACK;

    /*用于保存操作符*/
    StackInfo_st ops;
    ops.topOfStack = TOP_OF_STACK;
    int index = 0;
    /*用于标记,判断上一个是否为数字*/
    int flag = 0;
    int temp = 0;
    int op ;
    while(0 != *exp)
    {   
        /*如果是数字*/
        if(isdigit(*exp))
        {
            printf("char is %c\n",*exp);
             /*如果上一个还是数字,则取出栈顶数据*/
            if(1 == flag)
            {

                stack_pop(&nums,&temp);
                printf("pop from stack num %d\n",temp);
            }
            else
                temp = 0;
            flag = 1;
            temp = 10 * temp + *exp-'0';
            printf("push %d to stack\n",temp);
            stack_push(&nums,temp);
        }
        /*如果是操作符*/
        else if('/' == *exp || '*' == *exp || '+' == *exp || '-' == *exp)
        {
            flag = 0;
            printf("OP is %c\n",*exp);
            while((ops.topOfStack > TOP_OF_STACK )&&(SUCCESS == stack_top(&ops,&op))&&'(' != op && ')'!=op&&(priorityCompare(*exp,op) < 0))
            {
                calcOp(&nums, &ops,*exp);
            }
            printf("push %c to stack ops\n",*exp);
            stack_push(&ops,*exp);
        }
        /*左括号直接入栈*/
        else if('(' == *exp )
        {
            printf("push ( to stack ops\n");
            flag = 0;
            stack_push(&ops,*exp);
        }
        /*右括号,计算*/
        else if(')' ==*exp )
        {
            printf("deal with  ) in ops\n");
            flag = 0;
            /*右括号时,不断计算,直到遇见左括号*/
            while(SUCCESS == stack_top(&ops,&op) && '(' != op)
            {
                calcOp(&nums, &ops,*exp);
            }
            stack_pop(&ops,&op);
        }
        else
        {
            flag=0;
        }
        printf("flag is %d\n\n",flag);
        exp++;
    }
    /*计算剩余两个栈的内容*/
    while((!stack_is_empty(&ops)) && (!stack_is_empty(&nums)))
    {
        if(!calcOp(&nums, &ops,0))
        printf("exp is error\n");
    }
    stack_pop(&nums,&temp);
    /*如果栈中还有内容,说明表达式错误*/
    if((!stack_is_empty(&ops)) || (!stack_is_empty(&nums)))
        printf("\n\nexp is ok\n\n");

    if(SUCCESS == stack_pop(&nums,&temp))
        printf("result is %d\n",temp);
    *result = temp;
    return 0;
}

总结

本文介绍了利用栈对中缀表达式进行求值,而代码实现还有很多不足之处,例如对表达式的正确性校验不足,只能处理正整数等等,欢迎在此基础上完善补充。尽管如此,整个过程对使用栈进行中缀表达式的求值做了一个较为完整的介绍,因此具有一定的参考性。

本文分享自微信公众号 - 编程珠玑(shouwangxiansheng)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏浪子编程走四方

MySQL中不得不提的事务处理

记得前些日子分享过一篇有关MySQL中事务的知识点,但当时对MySQL中的事务只是纯粹的知道如何使用,缺乏对理论的进一步认识,抽时间单独去了解了一下,便在做一个...

8600
来自专栏JiekeXu之路

Windows10系统盘清理实用攻略

随着SSD的流行,如今很多DIY组装电脑或者笔记本都会配备固态硬盘,但目前SSD容量比较小,多为120-240GB左右,很多朋友为了省钱,电脑只有一块固态硬盘。...

32820
来自专栏AI科技时讯

10分钟学会使用YOLO及Opencv实现目标检测(下)|附源码

在上一节内容中,介绍了如何将YOLO应用于图像目标检测中,那么在学会检测单张图像后,我们也可以利用YOLO算法实现视频流中的目标检测。

10320
来自专栏Super 前端

JavaScript客户端存储

版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

10420
来自专栏Java后端技术栈cwnait

再也不敢使用集合默认初始化值了

集合初始化通常进行分配容量、设定特定参数等相关工作。我们以使用频率相对较高的ArrayList和HashMap为例,简要说明初始化的相关工作,并解释为什么在任何...

11530
来自专栏go

golang 中获取字符串个数

在 golang 中不能直接用 len 函数来统计字符串长度,查看了下源码发现字符串是以 UTF-8 为格式存储的,说明 len 函数是取得包含 byte 的个...

8270
来自专栏JiekeXu之路

关系型数据库 MySQL 之 InnoDB 体系结构

InnoDB 存储引擎是 MySQL 5.5 版本后的默认存储引擎,支持事务 ACID,回滚,系统崩溃恢复能力及多版本并发控制的事务安全,主要用于 OLTP 数...

11610
来自专栏AI科技时讯

被神话的大数据——从大数据(big data)到深度数据(deep data)思维转变

自从阿法狗战胜人类顶级棋手之后,深度学习、人工智能变得再一次火热起来。有些人认为,深度学习的再一次兴起是源于硬件的提升、数据量的增多以及高效...

7330
来自专栏JiekeXu之路

关系型数据库 MySQL 体系结构详解

通过前面几篇文章学会如何安装 MySQL 以及基础知识后,我们还需要学习体系结构,MySQL 和 Oracle 体系结构类似,如果学过 Oracle 可以类比记...

17320
来自专栏ICT售前新说

计算虚拟化2-虚机迁移

在云数据中心环境中虚机迁移是最常见的,可通过管理员手工迁移以及通过虚机自动感知服务器负载来动态迁移,无论哪种迁移方式都要尽量做到迁移前后用户无感知,...

10020

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励