高级编程通关练习题 #2:解析数学表达式

以字符串形式给定一条有效的数学表达式,使用字符串解析的方式计算该表达式的结果。注意不能使用 eval 方法来得出结果。

表达式的规则如下:

  • 表达式里可能出现的数学操作符为:加(+)、减(-)、乘(*)、除(/)
  • 可能的数值包括正负数和小数
  • 需要分析可能出现的多重小括号,譬如:(15 * (9.5 + 6)- -10)/ 4
输入样例:

“(-7 * -(16 / 4)) * (9.5 – 4.5)”

输出样例:

140.0

算法思路:

  • 方法一:可以采用数据结构stack来逐一处理每个字符
    • 如果字符是数字或小数点,则添加到到临时字符串变量A中。如果字符不是数字或者小数点,则把临时变量A中的字符串转换成数字,然后压栈。
    • 如果是字符是数学操作符加减乘除或左小括号,就把该字符压栈。
    • 如果字符是右小括号,那么需要从栈顶弹出数值和操作符保存到临时变量B,直到遇到左小括号为止,然后将字符串B做数学计算。
    • 数学计算的顺序如下:先计算除法,然后计算乘法,接下来计算减法,最后计算加法。
    • 字符串循环读取完毕后,检查stack栈内是否为空,如果不为空则需要将栈内内容重复上面第三项操作。
  • 方法二:使用正则表达式来解析字符串
    • 以左右小括号为标志先后解析需要计算的表达式
    • 提取数学操作符和数值后做相应处理