Arithmetic Expression Calculator

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

git clone https://git.scratko.xyz/arithmetic-expression-evaluator
cd arithmetic-expression-evaluator
make

Run the program:

./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