Digital Electronics

背景

学习数字电路的基础是建立在大家理解 Bit-String Flicking 以及 Boolean Algebra 上的，如果不了解这两个的话建议看一下这篇文章

定义

名字	图像	代数表达式	真假表格
BUFFER		X = A	输出 输出 0 0 1 1
NOT		X = A	输出 输出 A X 0 1 1 0
AND		X = AB 或者 A ・ B	输出 输出 A B X 0 0 0 0 1 0 1 0 0 1 1 1
NAND		X = AB 或者 A ・ B	输出 输出 A B X 0 0 1 0 1 1 1 0 1 1 1 0
OR		X = A+B	输出 输出 A B X 0 0 0 0 1 1 1 0 1 1 1 1
NOR		X = A+B	输出 输出 A B X 0 0 1 0 1 0 1 0 0 1 1 0
XOR		X = A ⊕ B	输出 输出 A B X 0 0 0 0 1 1 1 0 1 1 1 0
XNOR		X = ~(A ⊕ B) 或 A ⊙ B	输出 输出 A B X 0 0 1 0 1 0 1 0 0 1 1 1

解释

1. 图像后面有点就代表NOT
2. 比较尖的是OR
3. 尖的前面有一条弯的是XOR

Prefix/Infix/Postfix Notation

背景

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈遵循后进先出（LIFO-last in first out）——最后插入的元素最先出来。

中缀表达式

中缀表达式就是我们正常数学计算中所运用的式子，比如3 + 4 × 2 = 11

中缀表达式转前缀表达式（逆波兰式）

前缀表达式就是这样的式子：- × + 3 4 5 6，换成中缀表达式就是(3 + 4) × 5 - 6
转化遵循以下步骤：

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从右至左扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
     (4-1)如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
   (4-2)否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
     (4-3)否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1
5. 中新的栈顶运算符相比较；
     (5)遇到括号时：
     (5-1)如果是右括号“)”，则直接压入S1；
     (5-2)如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，
   (5-3)直到遇到右括号为止，此时将这一对括号丢弃；
6. 重复步骤(2)至(5)，直到表达式的最左边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

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

注：最后要按照栈的顺序（先进后出）输出

中缀表达式转后缀表达式（波兰式）

与转换为前缀表达式相似，遵循以下步骤：

1. 初始化两个栈：运算符栈 S1 和储存中间结果的栈 S2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压入 S2；
4. 遇到运算符时，比较其与 S1 栈顶运算符的优先级：
   (4-1) 如果 S1 为空，或栈顶运算符为左括号 “(”，则直接将此运算符入栈；
   (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入 S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
   (4-3) 否则，将 S1 栈顶的运算符弹出并压入到 S2 中，再次转到 (4-1) 与 S1 中新的栈顶运算符相比较；
5. 遇到括号时：
   (5-1) 如果是左括号 “(”，则直接压入 S1；
   (5-2) 如果是右括号 “)”，则依次弹出 S1 栈顶的运算符，并压入 S2，直到遇到左括号为止，此时将这一对括号丢弃；
6. 重复步骤 (2) 至 (5)，直到表达式的最右边；
7. 将 S1 中剩余的运算符依次弹出并压入 S2；
8. 依次弹出 S2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。

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

前缀表达式与后缀表达式辨析

1. 两者符号分别在数字的前面和后面；
2. 中缀表达式转成两者时读取入栈的方向不一样；前缀是倒着读，后缀是正着读；
3. 两者转化时，前缀表达式符号是相同或大于栈顶符号就压入，但后缀表达式一定要大于栈顶符号才压入

优先级

Questions & Solutions

Digital Electronics

注：如果文中有什么问题，欢迎在评论区指出；有不懂的也可以在评论区提问哦！