полиморфный стек

Какой язык - непонятно. Зачем писать на языке с ручным освобождением памяти в 2015 году - тоже непонятно.

в стеке хранить структуру с двумя полями - на тип оператора и на массив аргументов (если твой ЯП гогно - С++ например и не содержит информации о типах то с каждым аргументом ее надо хранить вручную)

т.е. так

stack
 {op: '*', args:[{type:NUM, val:1}, {type:VEC, val:[1,2,4]}} 
 {op: '+', args:[{type:VEC, val:[1,4]}, {type:VEC, val:[1,2,4]}} 

хотя это уже не стек, в стеке просто структра - тип и значение и не парить моск

это студент

да я уже написал и сдел работу, мне просто интересно, есть ли более «здоровое» решение. мне на си без плюсов, у вас кстати размерность вектора определена или может быть любой?

и надо освобождать память, если получили vector.

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

то что в [ ] это вектор, его можно складывать или вычитать с вектором, но не с числом

В таком случае, расскажи, как ты вычитаешь 5*[3,2,1]-[1,2] ?

в общем для реализации изобрел полиморфный стек, который может хранить «оператор», «множитель», «вектор»

нужен стек который хранит пару OPERATOR:VALUE

например для выражения a+b*c считаем так:

PUSH NUL:NUL
PUSH a:+
PUSH b:*
PUSH c:NUL
/* приоритет операции "*" больше, чем NUL, потому считаем */
POP x
POP y
PUSH (y*x):NUL
/* опять считаем */
POP x
POP y
PUSH (y+x):NUL
/* в стеке остался только ответ в окружении терминаторов NUL */

я примерно так и сделал, только получилось все равно криво

N мерный вектор легко хранить в виде одномерного, его и аллоцировать проще (i в одномерном массиве = x + y * width для трехмерного аналогично)

есть ли более «здоровое» решение.

для C только функцию-«освобождатор»

Для C++ можно было сделать класс Number, и наследовать от него класс Vector. Функции операторов сделать виртуальными.

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

5*[3,2,1] = [3*5,2*5,1*5]

[15,10,5] - [1,2] = [15-1,10-2,5-0]

[14,8,5]

N мерный вектор легко хранить в виде одномерного

вот только многие алгоритмы обработки «порадуют» тебя такими вещами, как «поменять строки местами». Потому часто есть смысл хранить массив указателей на одномерные массивы. (для случая матриц, впрочем, менять «слои» в гиперкубе тоже приходится. И это жопа).

вот только многие алгоритмы обработки «порадуют» тебя такими вещами, как «поменять строки местами».

что один цикл это сложно?

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

почему нельзя считать число вектором с одним значением?

10+[1,2]→[10]+[1,2]→[11,2]

что один цикл это сложно?

нет, это очень долго и дорого (т.к. для обмена нужна временная строчка, иначе совсем уныло).

PS: матрицы часто бывают разрежёнными, Over9000×Over9000, и почти все числа там — нули. Тут тем более не получится хранить как «простой массив».

нет, это очень долго и дорого (т.к. для обмена нужна временная строчка, иначе совсем уныло).

по ты оптимизируешь свою программу, я уже будут в отпуске

матрицы часто бывают разрежёнными

А еще бывает 10 мерная матрица с размерностью в миллион и одним числом, надо это оптимизировать

быдлокодер detected

нет, это очень долго и дорого (т.к. для обмена нужна временная строчка, иначе совсем уныло).

по ты оптимизируешь свою программу, я уже будут в отпуске

твой говнокод вряд-ли взлетит. Например bzip2 сортирует матрицу размерностью 1000000×1000000 байтов.

А еще бывает 10 мерная матрица с размерностью в миллион и одним числом, надо это оптимизировать

не встречал. Видимо это твоя фантазия.

Зачем писать на языке с ручным освобождением памяти в 2015 году - тоже непонятно.

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

можно было сделать класс Number, и наследовать от него класс Vector

Вся суть ООП

В языках без типов-сумм удачного решения не выйдет.

Конечно со стеком неудобно работать, ведь тут нужно дерево. Которое AST же.

твой говнокод вряд-ли взлетит. Например bzip2

я не пишу bzip2, так что у меня не говнокод

не встречал. Видимо это твоя фантазия

т.е. твой мир ограничен только bzip2, все остальное моя фантазия.

Скорее вся суть людей, любящих срещивать ужа с ежом.

не называй говнокодеров людями

можно было сделать класс Number, и наследовать от него класс Vector

Вся суть ООП

а что тебе не нравится-то?

Делаете гетерогенный список и вперед:

data Scalar
data Vect

data Stack :: a -> [*] where
  Nil :: Stack a []
  ConsV :: Vector a -> Stack a b -> Stack a (Vect ': b)
  ConsS :: a -> Stack a b -> Stack a (Scalar ': b)

type family Elt a :: * where
   ELT Scalar a = a
   ELT Vect a = Vector a

pop :: Stack a (z ': zs) -> (ELT a z, Stack a zs)
...

Конечно со стеком неудобно работать, ведь тут нужно дерево. Которое AST же.

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

Ну можно конечно и построить JFF.

я не пишу bzip2

ты знаешь, я не удивлён.

не встречал. Видимо это твоя фантазия

т.е. твой мир ограничен только bzip2, все остальное моя фантазия.

у тебя серьёзные проблемы с головой. Кроме шуток.

ты знаешь, я не удивлён.

Ты заначит пишешь? тогда ты прав:

у тебя серьёзные проблемы с головой. Кроме шуток.

Ты заначит пишешь? тогда ты прав: у тебя серьёзные проблемы с головой. Кроме шуток.

с чего-бы это?

Ну хотябы потому что bzip2 уже давно написан.

сделать класс Number, и наследовать от него класс Vector

не, лучше унаследовать его от класса Taburetka

Ну хотябы потому что bzip2 уже давно написан.

только написан он очень давно. bzip --best требует «много» памяти, аж 1Мб (точнее 7600k), это по сегодняшним меркам — ни о чём. Вполне можно сделать «параллельный bzip2», потому-что такой «большой» объём памяти меньше чем кеши любого современного процессора, и в процессорах сегодня минимум 2 ядра.

у меня вышло так:

typedef struct vector {
	int n;
	int *d;
} vect_t;
typedef struct member member_t;
struct member {
	int type;
	union {
		char op;
		int mul;
		vect_t vector;
	} data;
	member_t *prev;
};
typedef struct stack {
	member_t *head;
} stack_t;

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

какой у тебя диагноз?

что тут мучительного? то что он у тебя pop может делать в разных местах и соотв. в разных местах надо постоянно `if(фигасе у нас стек){костылим освобождение памяти}` - так это вопрос архитектуры, а не алгоритма, по идее тебе надо для member сделать функцию member_free() которая будет принимать его и чистить если надо, но по хорошему - чистить должен тотже ктои аллоцировал .... (тогда создание member надо делать с member_create() - который _копирует_ vector, тогда передав его ты после создания сразу и очиашеь память а в векторе копия

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

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

что там мучится-то? У тебя же есть поле type, там ведь тип лежит, да? Ну вот и освобождай:

if(x->type==VECTOR)
  free(x->data.vector.d);

можно сделать анонимный union, тогда просто x->vector.d

ща кто-нить как предложит лисповый DSL для ваших задач :-) а ышшо сделать пачку классов C++ и транслировать ваши строчки в плюса простым sed`ом..

в общем для реализации изобрел полиморфный стек, который может хранить «оператор», «множитель», «вектор»

а всё от незнания матчасти :-) в документации flex/bison есть разобранный пример калькулятора со скобками и приоритетами операций. Вам единственное остаётся дополнить его типом «вектор» (или скаляры представить как вектора)

Мог бы сделать стек массивом. Проще же отслеживать underflow/overflow

typedef int NUMTYPE;

enum STACKITEM_TYPE
{
        SI_SCALAR,
        SI_VECTOR,

        SI_PLUS,
        SI_MINUS,
        SI_MUL
};

typedef struct scalar
{
        NUMTYPE val;
} scalar;

typedef struct vector
{
        size_t n;
        NUMTYPE *vals;
} vector;

typedef struct stack_item
{
        enum STACKITEM_TYPE type;
        union operand {
                scalar s;
                vector v;
        } operand;
} stack_item;

typedef struct stack
{
        size_t n;
        stack_item *items;
} stack;

надо постоянно `if(фигасе у нас стек){костылим освобождение памяти}` - так это вопрос архитектуры

именно. В данном случае тут код будет из нескольких строчек, и я не понимаю, на кой ляд тут делать функции push/pop? Их можно просто так написать, прямо в коде.

Десятое правило Гринспена для Factor

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

что-то не понял, может потом пойму

вот тебе мой наколеночный вариант

#include <stdio.h>
#include <assert.h>
#include <malloc.h>

struct stack_el_
{
	int* value;
	int operator;
	int prio;
	struct stack_el_* next;
};

typedef struct stack_el_ stack_el;

void free_se(stack_el* y)
{
	assert(y);
	free(y->value);
	free(y);
}

void do_operator(stack_el* x, const stack_el* y)
{
	printf("%d %c %d = ",
			x->value[0],
			x->operator,
			y->value[0]);
	switch(x->operator)
	{
		case '+':
			x->value[0] += y->value[0];
			break;
		case '*':
			x->value[0] *= y->value[0];
			break;
		default:
			assert(0);
	}
	printf("%d\n", x->value[0]);
	x->operator = y->operator;
	x->prio = y->prio;
}

void parsing(stack_el* y)
{
	static int ph = 0;
	y->value = malloc(sizeof(int));
	assert(y->value);
	switch(ph++)
	{
		case 0:
			y->value[0] = 2;
			y->operator = '+';
			y->prio = 1;
			break;
		case 1:
			y->value[0] = 3;
			y->operator = '*';
			y->prio = 2;
			break;
		case 2:
			y->value[0] = 4;
			y->operator = '*';
			y->prio = 2;
			break;
		case 3:
			y->value[0] = 5;
			y->operator = 0;
			y->prio = 0;
			break;
		default:
			assert(0);
	}
}

int main()
{
	stack_el* sp;
	sp = malloc(sizeof(stack_el));
	assert(sp);
	sp->next = NULL;
	sp->prio = 0;
	sp->value = NULL;
	stack_el* y = NULL;
	do{
		y = malloc(sizeof(stack_el));
		assert(y);
		parsing(y);
		// push y
		y->next = sp;
		sp = y;
		printf("sp->next: %d(%c):%d, sp: %d(%c):%d\n",
				sp->next->prio, sp->next->operator, sp->next->value? sp->next->value[0]: 0,
				sp->prio, sp->operator, sp->value? sp->value[0]: 0);
		while(sp->next->prio >= sp->prio)
		{
			// pop y
			y = sp;
			sp = sp->next;
			if(!sp->prio)	break;
			do_operator(sp, y);
			free_se(y);
		}
	}while(sp->prio);
	assert(sp);
	assert(!sp->next);
	printf("result: %d\n", y->value[0]);
	free_se(y);
	free_se(sp);
	return 0;
}

считает 2+3*4*5

Как можно писать такое УГ и при этом учить людей в треде?

Как можно писать такое УГ

ну ты же не осилил написать лучше?

И да, тебе что не понравилось-то?

считает 2+3*4*5

!!! очень тонкая под-бка тех кто код не смотрит :-)

в смысле? Вот выхлоп:

sp->next: 0():0, sp: 1(+):2
sp->next: 1(+):2, sp: 2(*):3
sp->next: 2(*):3, sp: 2(*):4
3 * 4 = 12
sp->next: 2(*):12, sp: 0():5
12 * 5 = 60
2 + 60 = 62
result: 62

Потому что в общем случае ни число от вектора ни вектор от числа не наследуются.

В крайнем случае можно рассматривать число как диагональную матрицу произвольного размера, а вектор как матрицу-столбик (если она справа от знака умножения) или как матрицу-строчку (если она слева от знака умножения).

Это один из адекватных способов обобщить понятия вектора и числа. Но даже при этом класс Matrix с привычным для линейной алгебры интерфейсом нельзя сделать для них базовым. В общем, это надо сидеть и продумывать.