back to scratko.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorscratko <m@scratko.xyz>2025-08-13 19:40:04 +0300
committerscratko <m@scratko.xyz>2025-08-14 02:00:22 +0300
commit454faf929425e6dadf524d732811b7b2e2838495 (patch)
treec52f8ad77b27ee6b5348c1051da2eedcde99fc92
parent80749242cc6aa604c6ee3a7e3169df73c14e55d2 (diff)
downloadarithmetic-expression-evaluator-master.tar.gz
arithmetic-expression-evaluator-master.tar.bz2
arithmetic-expression-evaluator-master.zip
Changed READMEHEADmaster
-rw-r--r--README.md101
-rw-r--r--arithmetic-expression-evaluator.png (renamed from arithmetic-expression-computator.png)bin17449 -> 17449 bytes
2 files changed, 49 insertions, 52 deletions
diff --git a/README.md b/README.md
index 9d44c48..7251b41 100644
--- a/README.md
+++ b/README.md
@@ -1,61 +1,58 @@
-# Arithmetic expression computator
+# Arithmetic Expression Calculator
-<img src="arithmetic-expression-computator.png" />
+<img src="arithmetic-expression-evaluator.png" alt="Program screenshot" />
## 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
+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.
-```
-git clone https://git.scratko.xyz/arithmetic-expression-computator
-cd arithmetic-expression-computator
+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
```
-Launch the program `./arith_exp`
-After starting, enter an arithmetic expression.
-Notes:
+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
-- 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.
diff --git a/arithmetic-expression-computator.png b/arithmetic-expression-evaluator.png
index 37a6e99..37a6e99 100644
--- a/arithmetic-expression-computator.png
+++ b/arithmetic-expression-evaluator.png
Binary files differ