3.2.1 进制转换

十进制整数 N 向其他进制数 d （二、八、十六）的转换是计算机实现计算的基础问题。

转换法则：除以d倒取余

该转换法则对应一个简单算法原理：n=( n div d ) * d + n mod d 其中：div 为整除预算，mod 为求余运算

image.png

3.2.2 括号匹配的校验

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即：

  1. （ [] ()）或 [ ( [] [] ) ]

  2. [ ( ] ) 为错误格式

  3. ( [ () ) 或 （()] 为错误格式

image.png

  • 可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，校验匹配情况。

  • 在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论

    • 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号。
    • 从栈中弹出的左括号与当前校验的右括号类型不同时，说明出现了括号交叉的情况。
    • 算术表达式输入完毕，但栈中还没有匹配的左括号，说明左括号多于右括号。

3.2.3 表达式求值

表达式求值是程序设计语言编译中一个最基本的问题，它的实现也需要运用栈。

这里介绍的算法是由运算符优先级确定运算顺序的对表达式求值算符———算符优先算法

表达式的组成

  • 操作数（operand）：常数、变量

  • 运算符（operator）：算术运算符、关系运算符和逻辑运算符。

  • 界限符（delimiter）：左右括弧和表达结束符

任何一个运算表达式都由操作数、算术运算符和界限符组成。后两者统称为算符。例如：# 3*（7-2）#

为了实现表达式求值。需要设置两个栈：

  1. 一个是算符栈 OPTR，用于寄存运算符

  2. 另一个称为操作数栈 OPND，用于寄存运算数和运算结果。

求值的处理过程是在自左到右扫描表达式的每一个字符

  • 当扫描到的是运算数，则将其压入栈 OPND

  • 当扫描到的是运算符时

    • 若这个运算符比 OPTR 栈顶运算符的优先级高，则入栈 OPTR，继续向前处理

    • 若这个运算符比 OPTR 栈顶运算符的优先级低，则从 OPND 栈中弹出两个运算数，从栈 OPTR 中弹出栈顶运算符进行运算，并将运算结果压入栈 OPND

  • 继续处理当前字符，知道遇到结束符为止

3.2.4 舞伴问题

假设在舞会上，男士和女士各自排成一排。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个算法模拟上述舞伴配对问题。

显然，先入队的男士或女士先出队配成舞伴。因此该问题具有典型的先进先出特性，可以用队列作为算法的数据结构。