美文网首页数据结构
四则运算表达式求值

四则运算表达式求值

作者: 挽弓如月_80dc | 来源:发表于2019-08-27 21:32 被阅读0次

1.引子

最近做项目的时候,遇到了一个需求,就是随机给出一个数学公式,公式中包含变量,让求出公式最终的结果。譬如这样的:

NSDictionary *dic = @{@"s1":@"3",@"s2":@"6",@"s3":@"2"};
NSString *description = @"s1 + s1 * (s2 + s1 ) * 2 + (s2 / s3)";{

让求出 description = 3 + 3(6+3)2+(6/2) = 60

刚开始一头雾水,计算机怎么去识别计算公式呢,对着公式发呆,越看越熟悉,想起来 原来前段时间在学习数据结构的时候见到过,就翻开了书,一切问题都迎刃而解了。不得不佩服前辈们的机智。

项目地址在这里 好厉害,可惜不是我写的,借鉴这位仁兄的传送门😂😂😂

2.解读

数学表达式求值是借助于栈的实现的,俗称后缀表示法定义,也被称为逆波兰表示。(因为是20世纪50年代 波兰的逻辑学家想到的 一种不需要括号的后缀表达法 所有的符号都是在要运算数字的后面出现) 以下为倒推,皆出自《大话数据结构》,感觉这本书写的太好了

2.1 后缀表达式计算结果

对于9+(3-1)*3+10/2,用后缀表示法 应该是

9 3 1 - 3 * + 10 2 / +

计算规则:从左到有遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶的两个数字出栈,进行计算,再将运算结果进栈,一直到最终获得结果。

    1. 初始化一个空栈。此栈用来对要运算的数字进出使用。
    1. 后缀表达式中前三个都是数字,所以931进栈
    1. 接下来是 - 所以将占中的1出栈作为减数,3作为被减数,并将运算3-1得到的2 再进栈
    1. 接下来是数字3 进栈
    1. 后面是 * 也就意味着栈中的3和2出栈, 2*3 = 6,将6进栈
    1. 下面是 + 所以6和9出栈 9+6=15,将15进栈
    1. 接下来是102两个数字进栈
    1. 接下来是符号/ 栈顶的2与10出栈,10/2 = 5,再进栈
    1. 最后一个是符号+ 所以15与5出栈 5+15 = 20
    1. 结果是20出栈,栈变为空

      利用后缀表达法可以很顺利解决计算的问题,那么问题来了
      9+(3-1)*3+10/2 是如何转化为 9 3 1 - 3 * + 10 2 / + ,请往下看
2.2 中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式,即9+(3-1)*3+10/2叫做中缀表达式。因为所有的运算符号都在两数字的中间,现在的问题就是中缀转后缀了

中缀表达式 `9+(3-1)*3+10/2` 转化为后缀表达式 `9 3 1 - 3 * + 10 2 / + ` 

从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优于加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止

    1. 初始化一空栈,用来对符号进出栈使用
    1. 第一个字符是数字9, 输出9,后面是符号 + ,进栈
    1. 第三个是字符 ( ,依然是符号,因其只是左括号,还未配对,故进栈
    1. 第四个是数字3, 输出, 表达式为 9 3 ,接着是 -,进栈
    1. 接下来是数字1,输出,表达式为 9 3 1,后面是符号),此时,我们需要去匹配此前的(,所以栈顶依次出栈,并输出,直到( 出栈为止。
      此时括号上方只有-,因此输出,表达式变为 9 3 1 -
    1. 接着是数字3,输出,总的表达式为9 3 1 - 3. 紧接着是符号*,因为此时的栈顶符号为+,优先级低于*,所以不输出,*进栈
    1. 之后是符号+ 此时当前栈顶元素*比这个+的优先级高,因此栈中元素出栈并输出(没有比 '+' 号更低的优先级,所以全部出栈),总表达式为9 3 1 - 3 * +. 然后将当前这个符号+进栈。 请注意此处的+是中缀式子中的最后一个+。因为此前的都清空了
    1. 紧接着是数字10,输出。 表达式变为 9 3 1 - 3 * + 10,后是符号/,所以进栈
    1. 最后一个是数字2,输出,总的表达式为9 3 1 - 3 * + 10 2
    1. 因已到最后,所以将占中符号全部出栈并输出最终输出的结果为 9 3 1 - 3 * + 10 2 / +

3 总结

从刚才的推导中你会发现,要想计算机具有我们常规的处理逻辑
最重要的就两步:

1. 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)
2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)

相关文章

  • Java数据结构-栈-简单应用

    1,三种表达式 1)三种表达式四则运算的三种表达方式,用于四则运算表达式求值中缀表达式:(3+4)*5-6后缀表达...

  • 一些算法题

    1.四则运算表达式求值: 两个栈存储,中缀表达式转为后缀表达式 okcalculate1 & calculate2...

  • 四则运算(JAVA)

    计算过程 1.将四则运算串分割出中缀表达式2.将中缀表达式转换为后缀表达式3.对后缀表达式进行求值得出结果

  • 数据结构(四):栈的应用之表达式求值

    1、表达式求值 问题描述: 用户从控制台输入一个数学表达式(所有输入均合法),数学表达式只包含四则运算,程序需输出...

  • 表达式求值

    表达式求值

  • 大话数据结构 - 栈

    代码GitHub地址 栈的分类 栈是特殊的线性表 栈的典型应用递归,四则运算表达式求值。 栈的分类有两种: 静态栈...

  • LeetCode-150-逆波兰表达式求值

    LeetCode-150-逆波兰表达式求值 150. 逆波兰表达式求值[https://leetcode-cn.c...

  • 2017/3/13 周一

    GET 栈1.顺序栈/链式栈2.栈的递归用法3.栈的四则运算表达式求值(中缀表示法、后缀表示法)4.Java用St...

  • C语言的基于栈实现的表达式求值

    一、目的 理解中缀表达式求值的过程 理解中缀转后缀表达式求值的过程 掌握堆栈的应用 二、问题描述 缀表达式,其中包...

  • C语言的基于栈实现的表达式求值

    一、目的 理解中缀表达式求值的过程 理解中缀转后缀表达式求值的过程 掌握堆栈的应用 二、问题描述 缀表达式,其中包...

网友评论

    本文标题:四则运算表达式求值

    本文链接:https://www.haomeiwen.com/subject/lljyectx.html