How to Build a Calculator

1 Overview

Calculator is a common tool for us to get the arithmetic expression's result. In *NIX OS, once you type bc command, then you get into bc environment. Feel free to input any legal arithmetic expressions.

bc 1.06

Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.

......

APUE

1 前言

UNIX环境高级编程是一本久负盛名的书籍,本博客系列将会重点学习本书并附上学习笔记。为了尝试书中的代码,在 MacOS 操作系统如下操作:

下载页面

解压 src.3e.tar.gz

cp ./include/apue.h /Library/Developer/CommandLineTools/usr/include

cp ./lib/error.c /Library/Developer/CommandLineTools/usr/include

修改 apue.h 文件,在 #endif 之前插入 #include "error.c"

2 基......

ARTS(35)

1 Algorithm

设计一个数据结构,在下面的操作时间复杂度都是 $O(1)$

- insert(val): 当元素 val 不存在,向集合中插入该项。

- remove(val): 当元素 val 存在,从集合中删除该项。

- getRandom: 随机返回集合中一项,每个元素都有相同的概率返回。

对于 insert 和 remove 操作,使用 map 数据结构可以很容易实现;但是 getRandom 操作不能在 $O(1)$ 时间复杂度完成,因此要借助数组才能满足条件。

上图为依次往集合中添加 6、10、1、5、9 元素,下面是数组,用来依次保存数据;上......

ARTS(34)

1 Algorithm

一个数独的解法需遵循如下规则:

1:数字 1-9 在每一行只能出现一次。

2:数字 1-9 在每一列只能出现一次。

3:数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

对于一个数独表格,总共有 $81(9 \times 9)$ 个表格,索引为 0-80,所以对于每一个索引位置对应的行、列和块索引分别为:

row = i / 9

col = i % 9

block = row / 3 * 3 + col / 3

采用 DFS 方式没分别尝试各个空白位置,然后分别检查该位置是否满足数独的要求,如果无法满足,则进行回......

ARTS(33)

1 Algorithm

输入一个字符串,包含了 +, -, *, / 和非负整数,请输出该计算表达式的值。

例如: 1 + 12 - 4 * 2,输出的结果就是 5。

算法要求我们编写一个类似计算器的函数,输入为表达式计算,输出为表达式的值。如果写过编译器,这个问题不难,只要构建出一个抽象语法树(AST, Abstract Syntax Tree) 即可。

写个编译器有点小题大做,可以借助栈结构完成同样的目的。创建两个栈,分别存放操作数(operand)和操作符(operator),当待入栈的操作符优先级比栈顶操作符优先级小,则将栈顶操作符出栈,并且从操作数栈出栈相应的操作......