Android简易计算器（三）——表达式运算逻辑讲解

秒速五厘米 2022-05-25 09:07 376阅读 0赞

最近在学安卓的相关知识，第一个demo做了一个简易计算器，功能仿手机上自带的计算器，没有加括号，简单的四则运算，支持长表达式运算。此篇重点讲解计算器的运算逻辑，如何处理长表达式运算。

虽然，此次的计算器没有加上括号的功能，但我为了练习，使用了处理这类表达式运算基本思路：**先将中缀表达式转换为后缀表达式，然后进行计算。**

#### 中缀表达式和后缀表达式 ####

--------------------

首先，我们需要何为中缀表达式，何为后缀表达式。  
  中缀表达式就是通常所说的算术表达式，比如 `(1+2)*3-4`。称它为中缀表示法是因为**每个操作符都位于其操作数的中间**。

Syntax: operand1 operator operand2
    Example: (A+B)*C-D/(E+F)

而在后缀表示法中，操作符位于操作数后面。后缀表示法也称 逆波兰表示法（reverse Polish notation，RPN），因其使表达式求值变得轻松，所以被普遍使用。

Syntax  : operand1 operand2 operator
    Example : AB+C*DEF+/-

与上面对应的还有一个前缀表达式，即操作符在操作数前面，这种表达式经常用于编译器设计方面，对于一般编码很少用到，故这里不做介绍，有兴趣的可以自行查找定义和转换规则。

Syntax  : operator operand1 operand2
    Example : -*+ABC/D+EF

#### 中缀表达式转换后缀表达式 ####

--------------------

本篇着重介绍中缀表达式转换到后缀表达式的过程，避免喧宾夺主，对后缀表达式怎么转换到中缀表达式不做介绍，有兴趣的自行查找资料。

基本步骤：

1.  初始化两个栈，运算符栈opStack 和 数字栈numStack；
2.  从左往右扫描，碰到数字，压入 numStack；
3.  遇到运算符，比较其与opStack栈顶运算符的优先级：  
    3.1 如果栈为空或栈顶运算符为 “)”，直接压入栈；  
    3.2 若优先级比栈顶运算符的高，也将运算符压入opStack；  
    3.3 否则，将 opStack 栈顶的运算符弹出并压入到 numStack 中；  
    3.4 重复进行 3.1 - 3.3；
4.  遇到括号时，进行下面的判定：  
    4.1 如果是右括号 “)”，直接压入 opStack;  
    4.2 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
5.  重复步骤 2 至 4，直到表达式的最右边；
6.  将 opStack 中剩余的运算符依次弹出并压入 numStack；
7.  依次弹出 numStack 中的元素并输出，结果即为中缀表达式对应的后缀表达式。

例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：

<table> 
 <thead> 
  <tr> 
   <th align="left">扫描到的元素</th> 
   <th align="left">numStack(栈底-&gt;栈顶)</th> 
   <th align="left">opStack (栈底-&gt;栈顶)</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">1</td> 
   <td align="left">1</td> 
   <td align="left">空</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">+</td> 
   <td align="left">1</td> 
   <td align="left">+</td> 
   <td align="left">opStack 为空，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">(</td> 
   <td align="left">1</td> 
   <td align="left">+ (</td> 
   <td align="left">左括号，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">(</td> 
   <td align="left">1</td> 
   <td align="left">+ ( (</td> 
   <td align="left">左括号，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">2</td> 
   <td align="left">1 2</td> 
   <td align="left">+ ( (</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">+</td> 
   <td align="left">1 2</td> 
   <td align="left"> 
    <ul> 
     <li> ( ( + </li> 
    </ul></td> 
   <td align="left">opStack 栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">3</td> 
   <td align="left">1 2 3</td> 
   <td align="left"> 
    <ul> 
     <li> ( ( + </li> 
    </ul></td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">)</td> 
   <td align="left">1 2 3</td> 
   <td align="left"> 
    <ul> 
     <li> 
      <ul> 
       <li> ( </li> 
      </ul> </li> 
    </ul></td> 
   <td align="left">右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr> 
   <td align="left">×</td> 
   <td align="left">1 2 3 +</td> 
   <td align="left"> 
    <ul> 
     <li> ( × </li> 
    </ul></td> 
   <td align="left">opStack 栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">)</td> 
   <td align="left">1 2 3 + 4 ×</td> 
   <td align="left">+</td> 
   <td align="left">右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr> 
   <td align="left">-</td> 
   <td align="left">1 2 3 + 4 × +</td> 
   <td align="left">-</td> 
   <td align="left">-与+优先级相同，因此弹出+，再压入-</td> 
  </tr> 
  <tr> 
   <td align="left">5</td> 
   <td align="left">1 2 3 + 4 × + 5</td> 
   <td align="left">-</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">到达最右端</td> 
   <td align="left">1 2 3 + 4 × + 5 -</td> 
   <td align="left">空</td> 
   <td align="left">opStack中剩余的运算符压入numStack</td> 
  </tr> 
 </tbody> 
</table>

“ `1+((2+3)×4)-5` ” → “ `1 2 3 + 4 × + 5 -` ”

#### 后缀表达式运算 ####

--------------------

再来讲讲如何运算后缀表达式，得到我们想要的结果。

基本步骤：

1.  初始化一个空堆栈
2.  从左到右扫描后缀表达式
3.  如果字符是一个数字，把它压入堆栈。
4.  如果字符是个运算符，弹出两个数字，执行恰当操作，然后把结果压入堆栈。
5.  到后缀表达式末尾，从堆栈中弹出结果。

我们来以上面得到的后缀表达式 “`1 2 3 + 4 × + 5 -`” 为例子：

<table> 
 <thead> 
  <tr> 
   <th align="left">扫描到的元素</th> 
   <th align="left">stack(栈底-&gt;栈顶)</th> 
   <th align="left">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">1</td> 
   <td align="left">1</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">2</td> 
   <td align="left">1 2</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">3</td> 
   <td align="left">1 2 3</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">+</td> 
   <td align="left">1 5</td> 
   <td align="left">弹出栈顶两个数字，进行 + 运算，结果压入栈</td> 
  </tr> 
  <tr> 
   <td align="left">4</td> 
   <td align="left">1 5 4</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">×</td> 
   <td align="left">1 20</td> 
   <td align="left">弹出栈顶两个数字，进行 × 运算，结果压入栈</td> 
  </tr> 
  <tr> 
   <td align="left">+</td> 
   <td align="left">21</td> 
   <td align="left">弹出栈顶两个数字，进行 + 运算，结果压入栈</td> 
  </tr> 
  <tr> 
   <td align="left">5</td> 
   <td align="left">21 5</td> 
   <td align="left">数字，直接入栈</td> 
  </tr> 
  <tr> 
   <td align="left">-</td> 
   <td align="left">16</td> 
   <td align="left">弹出栈顶两个数字，进行 － 运算，结果压入栈</td> 
  </tr> 
  <tr> 
   <td align="left">到最右边</td> 
   <td align="left">空</td> 
   <td align="left">弹出栈顶，得到运算结果 16</td> 
  </tr> 
 </tbody> 
</table>

经过这样一个流程算得 `"1+((2+3)×4)-5" = "1 2 3 + 4 × + 5 -" = 16`。这个方法很容易进行验算，对着步骤多进行几次运算，就可以理解了。下篇我会贴出此次简易计算器的全部逻辑代码。