自然方法计算表达式值

在处理表达式计算的问题时,通常会想到使用抽象语法树(AST)或逆波兰表达式(RPN)算法来评估表达式。然而,本文将展示一种更“自然”的方法来解决计算表达式值的问题。

理念

假设需要计算以下表达式:

1+3*(5-(8-4)+(2+3)^2)

如果使用纸和笔来计算,会从具有最高优先级的运算开始计算数值结果,然后逐步简化表达式,直到得到最终的数值:

1+3*(5-4+5^2)

1+3*(5-4+25)

1+3*26

1+78

79

编写的表达式计算器正是遵循这个理念,其中运算符的优先级是通过结合运算符的优先级和其嵌套级别来计算的。

运算符优先级

每个算术运算符都被赋予了一个基础优先级。

优先级

  • + -> 1
  • - -> 1
  • * -> 2
  • / -> 2
  • ^ -> 3

如果运算符嵌套在括号内,其优先级等于基础优先级加上括号级别乘以10。

实现

实现过程遵循几个步骤:

格式化过程将输入字符串转换为遵循某些规则的字符串。例如,消除空格,将像2(3+1)这样的表达式转换为2*(3+1)等。此外,如果输入字符串以非加号或减号的运算符开头,它将抛出异常。

标记化过程接受格式化后的表达式,并产生:

  • 包含标记(tokens)的数组。
  • 包含每个运算符优先级的数组。
  • 包含优先级列表的数组。这个数组将被排序,将从最高优先级开始简化过程。

假设需要评估以下表达式字符串:

-5+2*(1+((7/8^2)-12^(-2))+9/4)

格式化后,字符串将被转换为:

0-5+2*(1+((7/8^2)-12^(0-2))+9/4)

标记化过程将创建这三个数组:

  • _tokens
  • _tokenPriority
  • _priorityValues

再次回顾一下运算符优先级的计算方式:

  • + -> 1
  • - -> 1
  • * -> 2
  • / -> 2
  • ^ -> 3

然后,加上运算符所在的括号级别乘以10。

_priorityValues数组被排序,从最高值(在例子中是33)开始,_tokens数组中的所有运算符都被计算,然后它们被替换为计算结果。因此,_tokens和_tokenPriority数组从:

[初始状态]

转变为:

[最终状态]

等等,直到得到最终结果。

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485