1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
# Arithmetic expression computator
<img src="arithmetic-expression-computator.png" />
## Introduction
Remarkably, this program is written in C without using library features at all.
This means that even the standard C library is not involved in the program. One
of the main properties of C language is zero runtime. This term emphasizes zero
size of the runtime library, i.e. the part of the library that is necessarily
contained in all executable files created by a particular compiler.
Assembler modules are written for program entry point and system call wrappers.
For writing and reading (standard output/input stream) -- `sys_read` and
`sys_write`. Also to terminate the program with a return code (assume in case of an
error) -- `sys_exit`. In addition, a primitive dynamic memory (heap) management
system is created. When an element is added to the stack, it checks the
availability of free addresses in the heap (which were previously allocated but
then freed). When an element is removed from the stack, the current address
from the heap is marked free so that it can be occupied later.
Assembler functions `sys_alloc` and `sys_free` are written to allocate and free
memory. They invoke system call brk(), which has number 45.
## About algorithm
This program is based on two algorithms: reverse polish notation (RPN) and
Dijkstra's algorithm.
Any arithmetic expression can be calculated. To do this, the expression needs to
be represented in an RPN, in that operands are written first, then
the operation sign; operands can be any complex expressions.
For example, the expression `(x+y)*(1-z)` in RPN would be written as: x y + 1 z -
\*. All this is calculated using the stack.
To translate an arithmetic expression from traditional infix notation to RPN we
need to use Dijkstra's algorithm.
The stack is also used here, but a new one.
According to this algorithm, the initial expression is viewed from left to
right. The elements are written out either to the RPN stack or to the operation
stack (for Dijkstra's algorithm). While viewing the expression, open brackets
and operation symbols (in some cases) are inserted into the operation stack, and
operands as well as operation symbols (again, in some cases) are inserted into
the RPN stack. The algorithm is described in more detail in the book А.В.
Столяров "Программирование: введение в профессию" (том 1, ДМК Пресс, стр. 644).
## Building and usage
```
git clone https://git.scratko.xyz/arithmetic-expression-computator
cd arithmetic-expression-computator
make
```
Launch the program `./arith_exp`
After starting, enter an arithmetic expression.
Notes:
- the expression must not contain any space characters
- negative values must be surrounded by brackets
- you can see an example of the expression on the screenshot above.
|
