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
|
# Arithmetic Expression Calculator
<img src="arithmetic-expression-evaluator.png" alt="Program screenshot" />
## Introduction
This program is implemented entirely in C **without using any library functions** — not even the standard C library.
One of the key properties of the C language is the possibility of **zero runtime**, meaning there is no mandatory runtime library code embedded into the executable.
Two small assembler modules are used:
- **Program entry point** (`_start` in `start.asm`)
- **System call wrappers** (`sys_read`, `sys_write`, `sys_exit`, `sys_alloc`, `sys_free`)
`sys_read` and `sys_write` handle input/output from standard streams.
`sys_exit` terminates the program with a given return code (useful for signaling errors).
Dynamic memory is managed manually through a simple heap allocator, which reuses freed blocks when possible.
Memory allocation and deallocation are done using the `sys_alloc` and `sys_free` assembler functions, which call the Linux `brk()` system call (number 45).
## Algorithm Overview
The program is based on two classic algorithms:
- **Reverse Polish Notation (RPN) evaluation**
- **Dijkstra’s shunting-yard algorithm**
Any valid arithmetic expression can be evaluated. First, it is converted from **infix notation** (e.g., `(x+y)*(1-z)`) to **RPN** (`x y + 1 z - *`), where operands appear first and operators follow.
Evaluation is then performed using a stack.
The conversion to RPN is implemented via **Dijkstra’s shunting-yard algorithm**, which uses:
- An **RPN stack** (for output)
- An **operator stack** (for temporary storage of operations and parentheses)
The algorithm scans the input from left to right, pushing operands and some operators to the RPN stack, while others (and parentheses) go to the operator stack according to precedence rules.
For a detailed explanation, see:
*A.V. Stolyarov, “Programming: An Introduction to the Profession” (Vol. 1, DMK Press), p. 644*.
## Building & Running
```bash
git clone https://git.scratko.xyz/arithmetic-expression-evaluator
cd arithmetic-expression-evaluator
make
```
Run the program:
```bash
./arith_exp
```
Then enter an arithmetic expression.
## Notes
- Expressions must not contain spaces
- Negative numbers must be enclosed in parentheses, e.g. (-5)
- See the example in the screenshot above
|
