ACSL
Mark Chen |
10 Feb 2021
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
1. 前/中/后缀表达式 Pre/In/Post-fix Expression
1.0 词汇表
| 词语 | 意思 |
|---|---|
| Mathematical Expression | 数学表达式 |
| Operator | 运算符 |
| Operand | 运算符的运算对象 例如 2 + 3 中2 和3是Operand，+是Operator |
| Term | 一个运算符和运算对象构成的“项” 例如 max(2 + 4, 5, 7) 中，2 + 4是一个项，其中 2 和 4 是 2 + 4的运算对象，+是这一项的运算符max(6, 5, 7)也是一个项，其中6,5,7 都是运算对象，max是运算符 |
Greatest Common Factor (gcf) |
最大公约数 |
1.1 前中后缀表达式介绍
一共有三种形式的表达式 - 前缀，中缀，后缀表达式，这三种表达式的区别在于运算符和运算对象之间的位置关系，一般我们用的数学表达式都是中缀表达式。下面我用个例子来说明这三种表达式的具体区别
首先我们找到一个正常的（中缀，infix expression）数学表达式
\[(a + b) \times c\]我们可以在这个表达式中找到运算符和运算对象
\[\underbrace{(\underbrace{a}_{\text{Operand}} \underbrace{+}_{\text{Operator}} \underbrace{b}_{\text{Operand}})}_{\text{Operand}} \underbrace{\times}_{\text{Operator}} \underbrace{c}_{\text{Operand}}\]这个表达式叫做“中缀表达式”因为运算符在运算对象中间
现在我们看看$(a + b)\times c$的前缀表达式形式，也就是运算符在运算对象前面的形式
\[\underbrace{\times}_{\text{Operator}} \underbrace{( \underbrace{+}_{\text{Operator}} \underbrace{a}_{\text{Operand}} \underbrace{b}_{\text{Operand}})}_{\text{Operand}}\underbrace{c}_{\text{Operand}} \rightarrow \times\;(+\; a\;b)\]后缀表达式则是运算符在运算对象后的形式
\[\underbrace{(\underbrace{a}_{\text{Operand}} \underbrace{b}_{\text{Operand}} \underbrace{+}_{\text{Operator}})}_{\text{Operand}}\underbrace{c}_{\text{Operand}} \underbrace{\times}_{\text{Operator}} \rightarrow (a\;b\;+)\;\times\]*为什么我们需要前后缀表达式？
虽然我们在计算的时候中缀表达式是最适合的，但是对于计算机来说，使用前缀表达式或者后缀表达式计算反而更加方便（先知道要进行什么运算，再获得这个函数的参数 - 前缀表达式 / 先获得将要进行的计算的所有参数，再得知要求值的函数 - 后缀表达式）
1.2 表达式是一棵树
我们可以把一个表达式看作一个树状图，每个父节点是一个运算符，每个子节点是运算对象，对一颗树“求值”的过程就是重复算出叶子节点经过父节点计算后的值，直到整棵树只剩一个值的过程。
例如我们计算 $(1 + 2)\times 4$ 的过程可以这样表达：
1.3 快速转化
ACSL中关于前中后缀表达式的一个重要考点就是它们之间的快速转化
对于一个复杂的表达式，我们一般不能够像上面的例子一样直接看出来前/后缀表达式，在这种时候，我们就需要用到刚才将表达式与树状结构的等价联系了
如果我们要把这样一个前缀表达式转化为中缀表达式的话，如果直接分析其中的term会画很多时间并且很容易出错。为了快速转化与求值，我们可以先将前缀表达式转化为一个树然后再转化为中缀表达式
1.4 练习
1.4.1 Intermediate
练习
答案
1.4.2 Senior
练习
答案
2. 二进制字符串 Bit String Flickering
Bit String - 二进制字符串指一个只有0和1的字符串
这个章节主要考察队二进制字符串的一系列操作，包括 位运算，平移，循环等
2.1 二进制位运算 Bitwise Operation
Bit-wise Operation是指每一个bit和它对应的bit都会进行该运算
具体的运算有以下几种
| a | b |
a AND b 与运算 |
a OR b 或运算 |
a XOR b 异或运算 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| a |
NOT a 非运算 |
|---|---|
| 1 | 0 |
| 0 | 1 |
这些运算之间像加减乘除一样是有优先级的，具体的优先级划分如下（数值越小越优先）：
| 优先级 | 运算符 |
|---|---|
| 0 |
NOT (~) |
| 1 |
SHIFT, CIRCULATE
|
| 2 |
AND (&) |
| 3 |
XOR (⊕) |
| 4 |
OR (|) |
2.2 位移操作符 Shift Operation
2.2.1 指令结构
一个位移操作包括以下三个部分：
- 位移方向 (
LEFT/RIGHT) - 位移距离 (
k) - 位移对象（具体在哪个二进制字符串上进行位移操作）
在ACSL中，这三个部分会以这样的形式出现
\[\text{LSHIFT-}k\;\text{01001001}\\ \downarrow\\ \underbrace{\text{L}}_{1}\text{SHIFT-}\underbrace{k}_{2}\;\underbrace{\text{01001001}}_{3}\]2.2.2 操作方法
如果是左移$k$位的话：
删除原二进制字符串左边的$k$位，然后在字符串右边补齐$k$个0
Example: $\text{LSHIFT-}3\; \text{01001001}$
\[\text{LSHIFT-}3\; \text{01001001} \rightarrow 01001\color{red}{000}\]
如果是右移$k$位的话：
删除原二进制字符串右边的$k$位，然后在字符串左边补齐$k$个0
2.3 循环操作符
2.3.1 指令结构
一个循环操作符和位移操作符的结构很像，分为三个部分：
- 循环方向（
LEFT/RIGHT） - 循环距离（
k） - 循环对象（具体在哪个二进制字符串上进行循环操作）
在ACSL中，这三个部分会以这样下形式出现
\[\text{LCIRC-}k\; \text{01001001}\\ \downarrow\\ \underbrace{\text{L}}_{1}\text{CIRC-}\underbrace{k}_{2} \; \underbrace{\text{01001001}}_{3}\]2.3.2 操作方法
如果是左侧循环$k$位的话：
将原来的字符串分为两份，一份是左边$k$位，剩下的是另一份
将左边$k$位直接拼接在剩下那一份的右侧
Example: $\text{LCIRC-}3\; 01101011$
\[\text{LCIRC-}3\; 01101011 \rightarrow \text{LCIRC-}3\; \begin{array}{c|c}\color{red}{011}&01011\end{array} \rightarrow 01011\color{red}{011}\]
如果是右侧循环$k$位的话和左侧循环操作是一样的
2.4 练习题型
| Senior | Intermediate | |
|---|---|---|
| Evaluate Expression | 3, 5, 7, 11(Hex), 13, 15(Hex,Oct), 17, 19, 21, 24, 25, 27, 30, 33 | 1, 3, 4(Hex), 5, 7, 10, 11, 13, 15, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 |
| Solve Equation | 1, 6, 29, 34, 35 | |
| Number of Possibilities | 2, 4, 8, 10, 12, 14, 16, 18, 20, 22, 23, 26, 28, 31, 32, 34, 35 | 2, 6, 8, 12, 14, 16, 18, 20 |
| New Operator | 9 | 9 |
2.4.1 Intermediate
题目
答案
2.4.2 Senior
题目
答案
3. LISP Programming
$\text{LISP} \approx \text{Lost In Stupid Parentheses}$ 😀
LISP是一种编程语言，它有两个元素 - 操作符和操作对象
3.1 操作对象
操作对象分为两种：
| 类型 | 含义 | 例子 |
|---|---|---|
| Atom | 一个具体的值 |
J, Mark, 29, haha
|
| List | 一系列Atom / List 组成的序列（注意List是可以嵌套的） |
(Mark), (J, haha, Hello World)，(Example, (ListInList, (2)), 3)
|
还有一种特殊的对象叫做 NIL，它相当于Python的None， Java中的null，它既是Atom也是List
3.2 前缀操作
LISP使用前缀进行操作，也就是说操作符是在操作对象前的
也就是说如果我们有一个函数FN(a, (1, 2, 3), (1, (2, 3))) 的话，在 LISP 中，它的表达如下
3.3 自动求值与字面量
在LISP中，如果我想表达一个字符串MULT 2 3的话，我该如何表达而不让大家认为这是一条指令并且将MULT 2 3的结构 6 带入下一步运算呢？
为了解决这个歧义，LISP引入了一种叫做“字面量”的概念，在字符串MULT 2 3前加上一个'引号，说明这个被加引号的结构不需要求值计算
Example
SET 'a '(MULT 2 3) ; a 是一个拥有元素 MULT, 2 和 3 的List（拥有三个元素）SET 'a (MULT 2 3) ; a 是 (6) (一个拥有一个元素的list)
3.4 操作符
| Function | Explanation | Example |
|---|---|---|
SET |
将第二个参数赋值给第一个参数 |
SET 'a 6a = 6 |
SETQ |
将第二个参数赋值给第一个参数，第一个参数自动加一个'
|
SETQ a 6 和 SET 'a 6是一样的 |
EVAL |
返回给定参数的值 |
EVAL MULT 2 3 会返回 6
|
ATOM |
判断给定参数是否是 ATOM 对象，返回 True 或 NIL |
ATOM 'Mark -> TrueATOM (1 3) -> NIL |
REVERSE |
逆序，给定的LIST顺序颠倒过来 |
REVERSE (1 3 (2 3)) -> ((2 3) 3 1)
|
CAR |
返回给定LIST的第一个元素 |
CAR ((2 3) 3 1) -> (2 3)
|
CDR |
返回删除给定list中第一个元素后的list |
CDR ((2 3) 3 1) -> (3 1)
|
CONS |
将第一个参数插入第二个参数（一定是一个list）的第一位 |
CONS 'Mark (1 (2 3) 4)->('Mark 1 (2 3) 4)
|
ADD |
$a + b$ |
ADD 1 2 -> 3
|
MULT |
$a \times b$ |
MULT 2 3 -> 6
|
SUB |
$a - b$ |
SUB 5 4 -> 1
|
DIV |
$a / b$, 注意不是整除，不过题目一般会帮你凑好数字 |
DIV 4 2 -> 2
|
SQUARE |
$a^2$ |
SQUARE 3 -> 9
|
EXP |
$a^b$ |
EXP 2 3 -> 8
|
EQ |
返回 a == b 的结果（True / NIL） |
EQ 3 4 -> NIL |
POS |
如果第一个参数是正数，返回True，否则返回NIL |
POS 2 -> True |
NEG |
如果第一个参数是负数，返回True，否则返回NIL |
NEG 2 -> NIL |
3.5 练习
3.5.1 Intermediate
问题
答案
3.5.2 Senior
问题
答案
