Digital Electronics

背景

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

定义

名字图像代数表达式真假表格
BUFFERBuffer-gate-en.svg X = A
输出 输出
0 0
1 1
NOTNot-gate-en.svg X = A
输出 输出
A X
0 1
1 0
ANDAnd-gate.png X = AB 或者 A ・ B
输出 输出
A B X
0 0 0
0 1 0
1 0 0
1 1 1
NANDNand-gate-en.svg X = AB 或者 A ・ B
输出 输出
A B X
0 0 1
0 1 1
1 0 1
1 1 0
OROr-gate-en.svg X = A+B
输出 输出
A B X
0 0 0
0 1 1
1 0 1
1 1 1
NORNor-gate-en.svg X = A+B
输出 输出
A B X
0 0 1
0 1 0
1 0 0
1 1 0
XORXor-gate-en.svg X = A ⊕ B
输出 输出
A B X
0 0 0
0 1 1
1 0 1
1 1 0
XNORXnor-gate-en.svg 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” 转换为前缀表达式的过程如下:
prefix notation example

注:最后要按照栈的顺序(先进后出)输出

中缀表达式转后缀表达式(波兰式)

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

  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” 转换为后缀表达式的过程如下:
postfix notation example

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

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

优先级

Operator precedence

Questions & Solutions

Digital Electronics


注:如果文中有什么问题,欢迎在评论区指出;有不懂的也可以在评论区提问哦!