LINUX.ORG.RU

Си: Стэк

 ,


1

1

Задача (придумал сам): реализовать слегка навороченный стэк и стандартные арифметические операции (+ / * -) Так как писал исключительно для себя, не стал делать файл .h и документацию. На, если надо, могу расписать, что к чему.

Знающих людей прошу посмотреть приложенный исходник и высказать конструктивную критику, так как сам я не программист, не учусь на программиста и не работаю в этой сфере, по-этому спросить по существу некого.

P.S. компилируется : gcc -Wall -g stack.c -lm

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <float.h>
#include <math.h>
#include <ctype.h>

#define STACK_INIT  1024
#define STACK_ADD   1024

#define BUFFER_INIT 4096
#define BUFFER_ADD  4096

enum type_expression {type_char, type_string, type_double};

struct stack_atom
{
    int type_data;
    int buffer_offset;
};

typedef struct stack_atom s_atom;

s_atom *stack;
char *data_buffer;

ptrdiff_t stack_size, top_element, buffer_size, buffer_top;

void stack_init(void)
{
    stack_size = STACK_INIT;
    buffer_size = BUFFER_INIT;
    if(!(stack = (s_atom*)malloc(stack_size * sizeof(s_atom))))
    {
        fputs("ERR : Cannot initialize stack\n", stdout);
        exit(1);
    }
    if(!(data_buffer = (char*)malloc(buffer_size * sizeof(char))))
    {
        fputs("ERR : Cannot initialize buffer\n", stdout);
        exit(2);
    }

    top_element = 0;
    buffer_top = 0;
}

void check_push(int add)
{
    if(top_element == stack_size)
    {
        stack_size += STACK_ADD;
        if(!(stack = (s_atom*)realloc(stack, sizeof(s_atom) * stack_size)))
        {
            fputs("ERR : Cannot reallocate stack\n", stdout);
            exit (3);
        }
    }
    if(buffer_top + add >= buffer_size)
    {
        buffer_size += BUFFER_ADD + add;
        if(!(data_buffer = (char*)realloc(data_buffer, sizeof(char) * buffer_size)))
        {
            fputs("ERR : Cannot reallocate data buffer\n", stdout);
            exit(4);
        }
    }
}

void push_char(char c)
{
    check_push(sizeof(char));

    stack[top_element].type_data = type_char;
    stack[top_element].buffer_offset = buffer_top;

    *(data_buffer + buffer_top) = c;

    ++buffer_top;
    ++top_element;
}

void push_double(double n)
{
    check_push(sizeof(double));

    stack[top_element].type_data = type_double;
    stack[top_element].buffer_offset = buffer_top;

    *((double *)(data_buffer + buffer_top)) = n;

    buffer_top += sizeof(double);
    ++top_element;
}

void push_string(char* str)
{
    int length = strlen(str);
    check_push(length + 1);

    stack[top_element].type_data = type_string;
    stack[top_element].buffer_offset = buffer_top;

    strncpy ((data_buffer + buffer_top), str, length);
    data_buffer[buffer_top + length + 1] = 0;

    buffer_top += length + 1;
    ++top_element;
}

void push(char *data)
{
    double dbl;
    if(data[1] == '\0') //special case;
    {
        if(isdigit(data[0]))
        {
            push_double((double)(data[0] - '0'));
            return;
        }
        push_char(data[0]);
        return;
    }
    else if((dbl = atof(data)) != 0.0)
    {
        push_double(dbl);
        return;
    }
    else
        push_string(data);
}

void print_object(int element)
{
    switch(stack[element].type_data)
    {
        case type_char:
            printf("%c ", (char)(*(data_buffer + stack[element].buffer_offset)));
            break;
        case type_double:
            printf("%e ", *((double *)(data_buffer + stack[element].buffer_offset)));
            break;
        case type_string:
            printf("%s ", (data_buffer + stack[element].buffer_offset));
    }
}

void binary_operation(char operation)
{
    double op1, op2;
    if((stack[top_element - 1].type_data == type_string) ||
            (stack[top_element - 2].type_data == type_string))
    {
        puts("WARN: Operations + - * / not work with strings");
        return;
    }
    if(stack[top_element - 1].type_data == type_char)
        op1 = (double)((char)(*(data_buffer + stack[top_element - 1].buffer_offset)));
    else
        op1 = (double)(*((double *)(data_buffer + stack[top_element - 1].buffer_offset)));

    if(stack[top_element - 2].type_data == type_char)
        op2 = (double)((char)(*(data_buffer + stack[top_element - 2].buffer_offset)));
    else
        op2 = (double)(*((double *)(data_buffer + stack[top_element - 2].buffer_offset)));
    switch(operation)
    {
        case '+':
            op1 += op2;
            break;
        case '-':
            op1 -= op2;
            break;
        case '*':
            op1 *= op2;
            break;
        case '/':
            if(fabs(op2) <= DBL_EPSILON*fmax(fabs(op2), 0))
            {
                puts("WARN: Division by zero");
                return;
            }
            op1 /= op2;
    }
    top_element -= 2;
    buffer_top = stack[top_element].buffer_offset;
    push_double(op1);
}

void main_loop(void)
{
    char command[256];
    size_t temp;
    while(1)
    {
        scanf("%255s", command);
        if(!command[1])
        {
            switch(command[0])
            {
                case '+':
                case '-':
                case '*':
                case '/':
                    if(top_element < 2)
                    {
                        puts("WARN: Not enough elements");
                        continue;
                    }
                    binary_operation(command[0]);
                    continue;
                case '.':
                    if(!top_element)
                    {
                        puts("WARN: Stack empty");
                        continue;
                    }
                    --top_element;
                    buffer_top = stack[top_element].buffer_offset;
                    print_object(top_element);
                    continue;
                case '^':
                    temp = top_element;
                    while(temp)
                        print_object(--temp);
                    continue;
                case '$':
                    temp = 0;
                    while(temp < top_element)
                        print_object(temp++);
                    continue;
                default:
                    push(command);
                    continue;
            }
        }
        else if(!strncmp(command, "exit", 255))
            exit(0);
        else if(!strncmp(command, "obj", 255))
        {
            printf("%td ", top_element);
            continue;
        }
        else if(!strncmp(command, "max_obj", 255))
        {
            printf("%td ", stack_size);
            continue;
        }
        else if(!strncmp(command, "data", 255))
        {
            printf("%td ", buffer_top);
            continue;
        }
        else if(!strncmp(command, "max_data", 255))
        {
            printf("%td ", buffer_size);
            continue;
        }
        else
            push(command);
    }
}

int main(int argc, char *argv[])
{
    stack_init();
    main_loop();
    return 0;
}

конструктивную критику

Ээээ... а какой в ней смысл, если

так как сам я не программист, не учусь на программиста и не работаю в этой сфере

anonymous ()
Ответ на: комментарий от theNamelessOne

При ошибке в realloc там exit() стоит и уже пофиг на указатели

XZentus ()

это стеб какой-то, штоле? или в самом деле хобби? в любом случае, вот за такой код хочется воскресить инквизицию...

Vinill ★★ ()
Ответ на: комментарий от XZentus

Собирай марки, коллекционируй монеты. Вышивай крестиком, вяжи крючком. Разводи кроликов, выращивай орхидеи.

Программирование в качестве хобби - явно не для тебя.

anonymous ()
Ответ на: комментарий от anonymous

Да, это моя конструктивная критика, кстати говоря.

anonymous ()

STACK_ADD можно чуть наращивать тоже до разумного предела.

vertexua ★★★★★ ()
Ответ на: комментарий от anonymous

Хотя кто знает. Вот Леннарт практически такой же сишный говнокод генерит и ничо, плодами его жизнедеятельности многие пользуются, да ещё и нахваливают. Так что может быть в тебе растёт новый поттеринг.

anonymous ()
Ответ на: комментарий от lispfuerimmer

ну да, про лисп же тут еще не написали
ТС зареген сегодня, ты вчера....
вангую удаление топика как флейм

Vinill ★★ ()

Детально не разбирался, но вспоминается принцип KISS.

Читабельность «не очень», много malloc-ов и realloc-ов в коде.

dvl36 ()
    else if(!strncmp(command, "obj", 255))
        {
            printf("%td ", top_element);
            continue;
        }
        else if(!strncmp(command, "max_obj", 255))
        {
            printf("%td ", stack_size);
            continue;
        }
        else if(!strncmp(command, "data", 255))
        {
            printf("%td ", buffer_top);
            continue;
        }
        else if(!strncmp(command, "max_data", 255))
        {
            printf("%td ", buffer_size);
            continue;
        }


вот этот участок может понятнее через набор структур {строка-команда, указатель на функцию_исполнитель этой команды}  и универсальное поиск по образцу 
qulinxao ★★☆ ()

Аффтар, не пиши такой код. Ничего понять просто нельзя, не известно, что он делает, зачем это нужно и при чём тут стек.

Хотя бы расскажи что-нибудь

lispfuerimmer ()
Ответ на: комментарий от XZentus

Не падает же ничего!

Супер аргумент. Ты бы сказал, зачем это хотя бы нужно и что делает

lispfuerimmer ()
Ответ на: комментарий от dvl36

принцип KISS.

Слабо его представляю для именно такой постановки задачи

много malloc-ов и realloc-ов в коде.

2 malloc (инициализируют буфер и список объектов стэка только при запуске) и 2 realloc (увеличивают размер буфера или списка объектов стэков только при необходимости, проверка - при каждой попытке помещения объекта в стэк)

XZentus ()
Ответ на: комментарий от XZentus

а, если по такому принципу :) хотя я все равно не был бы так уверен :))

Vinill ★★ ()
Ответ на: комментарий от XZentus

Слабо его представляю для именно такой постановки задачи

Не знаю что там у тебя за задача, но стек реализуется значительно короче и проще.

2 malloc (инициализируют буфер и список объектов стэка только при запуске) и 2 realloc

Ну вот не надо это «размазывать» по коду. Вынеси отдельно и локализуй в одном месте.

dvl36 ()
Ответ на: комментарий от lispfuerimmer

Дело было вечером, делать было нечего... Собственно просто пришла в голову идея написать свой стек с блекдже... со строками и double'ами!

Общая идея - есть 2 массива - в один (stack) кладутся структуры, каждая из которых имеет 2 поля. одно указывает на тип объекта, а второе - на смещение в буфере (data_buffer), где валяется сам объект

enum type_expression - чтобы было понятно, что за объект

struct stack_atom - описывает объект поля: type_data - тип объекта; buffer_offset - смещение, по которому в буфере валяется объект

char *data_buffer - собственно указатель на буфер, где последовательно валяются объекты stack_size - текущий размер стэка top_element - указывает индекс следующего элемента (который еще не инициализирован) buffer_size - текущий размер буфера в байтах buffer_top - указывает индекс следующего байта буфера (который еще не инициализирован)

stack_init() - инициализация - первоначальное выделение памяти check_push(int add) - проверка перед помещением объекта размером add байт. Если места не хватит, добавляет памяти в буфер или стэк.

push_что_то_там() - непоследственно помещает объект в стэк push(char* data) - определяет, что за объект в data и вызывает соответствующий push_что_то_там()

print_object(int element) - печатает element из стэка

binary_operation(char operation) - проводит операцию + - / * между двумя верхними объектами стэка

XZentus ()
Ответ на: комментарий от dvl36

стек реализуется значительно короче и проще.

с учетом возможности поместить туда char'ы, строки произвольной длины и double?

Ну вот не надо это «размазывать» по коду. Вынеси отдельно и локализуй в одном месте.

Две соседние функции - одна для обоих malloc (stack_init) и одна для обоих realloc (check_push). А по 2 штуки их, так как отдельно существует буфер для данных, где хранятся объекты, и отдельно - список структур, указывающих на расположение и тип объектов. И где тут размазывание по коду?

XZentus ()
Ответ на: комментарий от XZentus

Тогда я бы советовал сделать интерпретатор собственного языка, где изначально была бы возможность узнать тип объекта в рантайме. А то зачем это для C даже в учебных целях - неизвестно.

lispfuerimmer ()
Ответ на: комментарий от XZentus

с учетом возможности поместить туда char'ы, строки произвольной длины и double?

KISS.

И где тут размазывание по коду?

Отдельно, прямо в main-е выдели много, и передавай указатель своему init-у, пускай он разруливает что кому. realloc-и в топку, не будет хватать напиши «Out of memory»

dvl36 ()

Проверяли, realloc в два раза медленнее alloc + memcpy.

inn ()
Ответ на: комментарий от XZentus

:)))
слушай, а ты хоть man читал к тем функциям, которые используешь? :))
у тебя 3хрен - ентер - 2падла - ентер - минус- ентер - точка - что получится? :))
это чисто про юзабельность.. :)))

Vinill ★★ ()
Ответ на: комментарий от gh0stwizard

1) ну и где там реализация ipush и cpop? 2) ну и где там возможность хранить строки?

Там проще задача поставлена.

XZentus ()

это стэк или таки калькулятор в обратной польской нотации или целая стэк машина? :))

stack[top_element - 1]

Эта операция на стэке называется peek()

struct stack_atom peek(unsigned idx) {
  return stack[top_element - idx];
}
Во-вторых нужна операция pop, извлекающая элемент из стэка т.к.:
    if(stack[top_element - 1].type_data == type_char)
...
    top_element -= 2;
    buffer_top = stack[top_element].buffer_offset;
    push_double(op1);
будет выглядеть так:
 stack_atom a1 = pop();
 if(a.type_data == type_char)
 ...
 push(result);
То есть принцип такой: Ты извлекаешь две верхних элемента из стэка, применяешь операцию и кладёшь резултат наверх.

Если ты хочешь сделать стэк-машину или калькулятор в обратной польской нотации, то операции тоже кладутся в стэк. То есть

push(op1)
push(op2)
push(add);

invy ★★★★★ ()
Ответ на: комментарий от invy

это стэк или таки калькулятор в обратной польской нотации или целая стэк машина? :))

Ну сначала хотелось просто модного стэка, потом пошло-поехало, а тут еще и про forth почитал. Как-то так.

Во-вторых нужна операция pop, извлекающая элемент из стэка

Она у меня просто отдельной функцией не вынесена, а так - строки

                case '.':
                    if(!top_element)
                    {
                        puts("WARN: Stack empty");
                        continue;
                    }
                    --top_element;
                    buffer_top = stack[top_element].buffer_offset;
                    print_object(top_element);
                    continue;

То есть принцип такой: Ты извлекаешь две верхних элемента из стэка, применяешь операцию и кладёшь резултат наверх.

сейчас так оно и есть

то операции тоже кладутся в стэк.

ага, вот тут у меня косяк

XZentus ()
Ответ на: комментарий от XZentus

Она у меня просто отдельной функцией не вынесена

А нужно. push и pop - две операции на стэке. Без них никуда, и потом их надо и использовать. Абстракция и don't repeat yourself :)

invy ★★★★★ ()
Ответ на: комментарий от dikiy

я хочу потренироваться в работе с указателями, данными переменной длины

XZentus ()

What The Fuck is this? ! ? Помнится в K&R был пример с реализацией калькулятора, который работает по принципу стека.

z00ke ()
Ответ на: комментарий от XZentus

теме ап хм, если бы вы с рождения следовали такой логике, то никогда не научились бы разговаривать и даже встать с кровати не смогли бы.

IvanR ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.