不用递归和栈的表达式计算

Aline744

计算机计算表达式，难点在于识别运算优先级。例如1 + 2 * 3，计算机必须识别出各个运算的优先级才能正确地进行运算。处理运算优先级的传统算法是构建逆波兰表达式，即将1 + 2 * 3改写为1 2 3 * +，将运算优先级凸显出来。但是其实计算表达式的算法不是唯一的，例如对于表达式1 + 2 * ( 3 + 4 )，我们可以标记出如下优先级：
1 + 2 * 3 + 4
0 1 0 2 0 7  0
标记规则是：无括号时，常数优先级为0，加减优先级为1，乘除优先级为2，有括号时，每多一组括号，优先级+5
按照这种规则，  1 * ( 2  + ( 3 + 4 ) ) 的优先级为
1 * 2 + 3 + 4
0 2 0 6 0  11  0
标记优先级后，优先处理高优先级的运算，再处理低优先级的运算，直到只剩下一个数字为止，例如上述表达式：
第一次计算：
1 * 2 + 7
0 2 0 6 0  
第二次计算
1 * 9
0 2 0
第三次运算
9
0

该算法的核心思想，其实是建立一个树结构，高优先级的运算对应树底层节点，低优先级的运算对应树根，每一次运算，都相当于从树底向上“爬”一次，当只剩下一个数时就意味着爬到了树顶，运算就完成了

aidn

和递归栈有何区别？能省什么？

dage1

谢谢楼主的分享

h5.weishi.qq.com/weishi/feed/7SYcBSlA71SxSNhc2
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBSlA71SxSNhc2
h5.weishi.qq.com/weishi/feed/7SYcBSlA71SxSMCcm
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBSlA71SxSMCcm
h5.weishi.qq.com/weishi/feed/7SYcCKTu51SxSKYaC
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCKTu51SxSKYaC
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCKTu51SxSK5uC
h5.weishi.qq.com/weishi/feed/7SYcAsevj1SxSKiO8
h5.weishi.qq.com/weishi/feed/7SYcCKTu51SxSK5uC
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcAsevj1SxSKiO8
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSJVgg
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCKTu51SxSJOOA
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSJVgg
h5.weishi.qq.com/weishi/feed/7SYcCKTu51SxSJOOA
h5.weishi.qq.com/weishi/feed/7SYcBSlA71SxSJN8E
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBSlA71SxSJN8E
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcAsevj1SxSJJMW
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSJK4K
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSJK4K
h5.weishi.qq.com/weishi/feed/7SYcAsevj1SxSJJMW
h5.weishi.qq.com/weishi/feed/7SYcBSlA71SxSJzCF
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBSlA71SxSJzCF
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSJzWc
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSJzWc
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcAsevj1SxSJscw
h5.weishi.qq.com/weishi/feed/7SYcAsevj1SxSJscw
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSJrGs
h5.weishi.qq.com/weishi/feed/7SYcCyj2S1SxSJi0k
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSJrGs
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCyj2S1SxSJi0k
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSJig4
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSJig4
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98ar1SxSJgOm
h5.weishi.qq.com/weishi/feed/7SYcC98ar1SxSJgOm
h5.weishi.qq.com/weishi/feed/7SYcBSlA71SxSJeOy
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBSlA71SxSJeOy
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSJbK4
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSJbK4
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCKTu51SxSJ74U
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98as1SxSJ0iq
h5.weishi.qq.com/weishi/feed/7SYcCKTu51SxSJ74U
h5.weishi.qq.com/weishi/feed/7SYcC98as1SxSJ0iq
h5.weishi.qq.com/weishi/feed/7SYcC98ar1SxSJ2mo
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98ar1SxSJ2mo
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSIY8m
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSIRQu
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSIRQu
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSIY8m
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98ar1SxSIQYo
h5.weishi.qq.com/weishi/feed/7SYcC98ar1SxSIQYo
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7g1SxSIJSC
h5.weishi.qq.com/weishi/feed/7SYcBco7g1SxSIJSC
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSIIw2
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSIIw2
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98ar1SxSIFE8
h5.weishi.qq.com/weishi/feed/7SYcC98ar1SxSIFE8
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBSlA71SxSID8c
h5.weishi.qq.com/weishi/feed/7SYcBSlA71SxSID8c
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSIEqy
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSIEqy
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98as1SxSIDmY
h5.weishi.qq.com/weishi/feed/7SYcC98as1SxSIDmY
h5.weishi.qq.com/weishi/feed/7SYczn69U1SxSIwES
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczn69U1SxSIwES
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSIvC6
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSIvC6
h5.weishi.qq.com/weishi/feed/7SYcC98ar1SxSIs4C
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98ar1SxSIs4C
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSIs4Y
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSIs4Y
h5.weishi.qq.com/weishi/feed/7SYcBco7g1SxSIksE
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7g1SxSIksE
h5.weishi.qq.com/weishi/feed/7SYcC98ar1SxSIjG2
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98ar1SxSIjG2
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSIjK8
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSIjK8
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSIgYA
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSIgYA
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcC98as1SxSIeqm
h5.weishi.qq.com/weishi/feed/7SYcC98as1SxSIeqm
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczn69U1SxSId6a
h5.weishi.qq.com/weishi/feed/7SYczn69U1SxSId6a
h5.weishi.qq.com/weishi/feed/7SYcBco7g1SxSI9u8
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7g1SxSI9u8
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSI76g
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSI76g
h5.weishi.qq.com/weishi/feed/7SYcCdkjv1SxSI2uS
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcCdkjv1SxSI2uS
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7g1SxSHXg2
h5.weishi.qq.com/weishi/feed/7SYcBco7g1SxSHXg2
h5.weishi.qq.com/weishi/feed/7SYczn69U1SxSHPs4
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczn69U1SxSHPs4
h5.weishi.qq.com/weishi/feed/7SYcBco7k1SxSHIsk
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7k1SxSHIsk
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczvus41SxSHH0e
h5.weishi.qq.com/weishi/feed/7SYczvus41SxSHH0e
h5.weishi.qq.com/weishi/feed/7SYcAo2ma1SxSHzEm
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcAo2ma1SxSHzEm
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcAo2ma1SxSHr6w
h5.weishi.qq.com/weishi/feed/7SYcAo2ma1SxSHr6w
h5.weishi.qq.com/weishi/feed/7SYcziU0O1SxSHoQA
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcziU0O1SxSHoQA
h5.weishi.qq.com/weishi/feed/7SYczvus41SxSHm8u
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczvus41SxSHm8u
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcBco7g1SxSHj80
h5.weishi.qq.com/weishi/feed/7SYcBco7g1SxSHj80
h5.weishi.qq.com/weishi/feed/7SYczvus41SxSHbkM
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczvus41SxSHbkM
h5.weishi.qq.com/weishi/feed/7SYcAo2ma1SxSH9uO
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcAo2ma1SxSH9uO
h5.weishi.qq.com/weishi/feed/7SYczvus41SxSH0CO
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczvus41SxSH0CO
h5.weishi.qq.com/weishi/feed/7SYcziU0O1SxSH6se
h5.weishi.qq.com/weishi/feed/7SYczavIA1SxSGVgM
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcziU0O1SxSH6se
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczavIA1SxSGVgM
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczeHRG1SxSGPeC
h5.weishi.qq.com/weishi/feed/7SYczeHRG1SxSGPeC
h5.weishi.qq.com/weishi/feed/7SYczvus41SxSGM0w
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczvus41SxSGM0w
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczn69U1SxSGL0M
h5.weishi.qq.com/weishi/feed/7SYczn69U1SxSGL0M
h5.weishi.qq.com/weishi/feed/7SYcziU0O1SxSGLA8
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcziU0O1SxSGLA8
h5.weishi.qq.com/weishi/feed/7SYczeHRG1SxSGzOY
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczeHRG1SxSGzOY
h5.weishi.qq.com/weishi/feed/7SYczn69U1SxSGsAs
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczn69U1SxSGsAs
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczeHRG1SxSGqsQ
h5.weishi.qq.com/weishi/feed/7SYczeHRG1SxSGqsQ
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczavIz1SxSGi06
h5.weishi.qq.com/weishi/feed/7SYczavIz1SxSGi06
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcz6jzp1SxSG6Qk
h5.weishi.qq.com/weishi/feed/7SYcz6jzp1SxSG6Qk
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczvus41SxSG4WY
h5.weishi.qq.com/weishi/feed/7SYczvus41SxSG4WY
h5.weishi.qq.com/weishi/feed/7SYcziU0O1SxSFXAm
h5.weishi.qq.com/weishi/feed/index.html?id=7SYcziU0O1SxSFXAm
h5.weishi.qq.com/weishi/feed/7SYczeHRI1SxSCYi0
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczeHRI1SxSCYi0
h5.weishi.qq.com/weishi/feed/index.html?id=7SYczeHRG1SxSCXeK
h5.weishi.qq.com/weishi/feed/7SYczeHRG1SxSCXeK

locky_z

生成树和遍历树的过程，也是用递归的方法。

Aline744

版主何在？楼上有发小广告的

koei

aidn 发表于 2024-7-28 09:40
和递归栈有何区别？能省什么？

增加了复杂度，啥也没有省

Aline744

dage1 发表于 2024-7-28 11:19
谢谢楼主的分享

h5.weishi.qq.com/weishi/feed/7SYcBSlA71SxSNhc2

你发的这些网址是什么东西？解释一下