diff options
| -rw-r--r-- | README.md | 22 | ||||
| -rw-r--r-- | arith_exp.c | 28 | ||||
| -rw-r--r-- | calls.h | 4 | ||||
| -rw-r--r-- | stack.c | 6 | ||||
| -rw-r--r-- | stack.h | 4 |
5 files changed, 41 insertions, 23 deletions
@@ -5,7 +5,24 @@ ## Introduction Remarkably, this program is written in C without using library features at all. -Assembler modules are used for program entry point and system call wrappers. +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. @@ -27,7 +44,7 @@ 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 usagea +## Building and usage ``` git clone https://git.scratko.xyz/arithmetic-expression-computator @@ -38,6 +55,7 @@ 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. diff --git a/arith_exp.c b/arith_exp.c index 8a4c002..c38c821 100644 --- a/arith_exp.c +++ b/arith_exp.c @@ -4,18 +4,18 @@ char buffer[BUF_SIZE]; -enum { +enum { success = 1, error = -1, base = 10 }; enum state { yes, no }; -static int is_higher_priority(const stack *operation_stack, +static int is_higher_priority(const stack *operation_stack, int current_operation) { int prev_operation = top_stack(operation_stack); - return (prev_operation == '+' || prev_operation == '-') && + return (prev_operation == '+' || prev_operation == '-') && (current_operation == '*' || current_operation == '/'); } @@ -41,7 +41,7 @@ static void make_operation(stack *rpn_stack, int operation) push_stack(rpn_stack, result); } -static long translate_to_number(const char *begin_address, int size, +static long translate_to_number(const char *begin_address, int size, enum state is_negative_number) { long number = 0; @@ -57,7 +57,7 @@ static long translate_to_number(const char *begin_address, int size, return number; } -static int extract_digit(const char *buf, long *number, int buf_length, +static int extract_digit(const char *buf, long *number, int buf_length, int *pos) { enum state is_negative_number = no; @@ -79,14 +79,14 @@ static int extract_digit(const char *buf, long *number, int buf_length, else return error; case ')': - if(is_negative_number == yes && + if(is_negative_number == yes && is_end_negative_expression == no) { is_end_negative_expression = yes; continue; } - *number = - translate_to_number(begin_address, number_length, + *number = + translate_to_number(begin_address, number_length, is_negative_number == yes ? yes : no); return ')'; case '+': @@ -95,7 +95,7 @@ static int extract_digit(const char *buf, long *number, int buf_length, case '/': case '\n': if(is_negative_number == yes || is_positive_number == yes) { - *number = translate_to_number(begin_address, number_length, + *number = translate_to_number(begin_address, number_length, is_negative_number == yes ? yes : no); return success; } else @@ -117,7 +117,7 @@ static int extract_digit(const char *buf, long *number, int buf_length, static void clean_operation_stack(stack *operation_stack, stack *rpn_stack) { int operation; - while(!is_empty_stack(operation_stack) && + while(!is_empty_stack(operation_stack) && top_stack(operation_stack) != '(') { operation = pop_stack(operation_stack); @@ -158,7 +158,7 @@ static void print_number(stack *rpn_stack) sys_write(1, string, i); } -static void buffer_process(const char* buffer, int length, stack *rpn_stack, +static void buffer_process(const char *buffer, int length, stack *rpn_stack, stack *operation_stack) { int top, pos, result; @@ -175,7 +175,7 @@ static void buffer_process(const char* buffer, int length, stack *rpn_stack, ++pos; continue; } - if(symbol == '\n' || symbol == ')' || symbol == '+' || symbol == '-' || + if(symbol == '\n' || symbol == ')' || symbol == '+' || symbol == '-' || symbol == '*' || symbol == '/') { push_stack(rpn_stack, operand); @@ -203,14 +203,14 @@ static void buffer_process(const char* buffer, int length, stack *rpn_stack, case '*': case '/': top = top_stack(operation_stack); - if(top == '(' || + if(top == '(' || is_higher_priority(operation_stack, buffer[pos])) { push_stack(operation_stack, buffer[pos]); ++pos; continue; } else { - while(top_stack(operation_stack) != '(' && + while(top_stack(operation_stack) != '(' && !is_higher_priority(operation_stack, buffer[pos])) { make_operation(rpn_stack, pop_stack(operation_stack)); } @@ -3,8 +3,8 @@ int sys_write(int fd, const void *buf, int size); int sys_read(int fd, void *buf, int size); -void* sys_alloc(int size); -void sys_free(void* p); +void *sys_alloc(int size); +void sys_free(void *p); void sys_exit(int code); extern int sys_errno; @@ -4,17 +4,17 @@ #define QUANTITY_ADDRESSES 5 enum address_control { get_address, set_address }; -void* heap_base; +void *heap_base; void init_stack(stack *st) { *st = 0; } -static void* address_management(void* address, enum address_control state) +static void *address_management(void *address, enum address_control state) { enum { null = 0 }; - static void* available_addresses[QUANTITY_ADDRESSES]; + static void *available_addresses[QUANTITY_ADDRESSES]; int i; if(state == set_address) { for(i = 0; i < QUANTITY_ADDRESSES; ++i) { @@ -5,13 +5,13 @@ struct item { long data; struct item *next; }; -typedef struct item* stack; +typedef struct item *stack; void init_stack(stack *st); void push_stack(stack *st, long num); long pop_stack(stack *st); int is_empty_stack(const stack *st); long top_stack(const stack *st); -extern void* heap_base; +extern void *heap_base; #endif |