| csbwalker |
01.06.2009 11:09 |
По просьбе Дарии - откомментрированная программа с построением дерева выражений:
Код:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* Структура для хранения элемента бинарного дерева */
struct element
{
int number; /* Хранимое число */
char operation; /* Код операции, которую необходимо выполнить что бы получить
из дочерних элементов число */
struct element *left; /* Указатель на левое поддерево */
struct element *right; /* Указатель на правое поддерево */
};
/* Функция для определения в строке позиции операции с наименьшим приоритетом (с учетом скобок) */
/* На входе - массив символов в котором хранится строка, количество символов в строке */
/* Примечание - при обработке строки не учитывается концевой 0-маркер, поэтому функция может обрабатывать
отдельные части строки */
int findLastOperation(char str[], int count)
{
int current = 0, pri, i, number, minimal = -1;
for(i = 0; i < count; i++) /* Обработка всех символов строки */
{
switch(str[i]) /* Действия в зависимости от кода текущего символа */
{
case '(':
current += 2; /* Скобка открывается. Увеличиваем базовый приоритет. */
break;
case ')':
current -= 2; /* Скобка закрывается. Уменьшаем базовый приоритет. */
break;
case '*':
case '/': /* Умножение и деление - приоритетные операции,
к базовому приоритету прибавляем 1 и проверяем, не является
ли приоритет текущей операции минимальным из уже просмотренных,
если да - обновляем указатель на минимальный и значение приоритет */
pri = current + 1;
if(((minimal >= 0) && (pri < minimal)) || (minimal < 0))
{
number = i;
minimal = pri;
}
break;
case '+':
case '-':
/* Действия аналогичны умножению и делению, но приоритет не увеличивается на 1 */
pri = current;
if(pri == 0) /* Если приоритет текущей операции 0 - то он заранее минимален, */
return i; /* поэтому можно не продолжать дальнейший поиск */
if(((minimal >= 0) && (pri < minimal)) || (minimal < 0))
{
number = i;
minimal = pri;
}
break;
default: /* Если символ - не операция */
break;
}
}
if(minimal >= 0)
return number; /* Возвращаем номер позиции */
else
return -1; /* Если minimal=-1 - то не было найдено ни одно операции */
}
/* Функция преобразования строки в целое число */
/* Учитывает возможность наличия открывающейся в начале или закрывающейся в конце скобки */
int stringtoi(char str[], int count)
{
char tmp[count + 1]; /* Временный буфер для строки */
while(str[0] == '(') /* Убираем все скобки в начале */
str++, count--;
while(str[count - 1] == ')') /* Убираем все скобки в конце */
count--;
strncpy(tmp, str, count); /* Копируем получившуюся после обрезки строку во временный буфер tmp */
tmp[count] = '\0'; /* Ставим концевой 0-маркер после строки в буфере, что бы получить стандартную C-строку */
return atoi(tmp); /* Возвращаем результат преобразования стандартной C-строки в целое число */
}
/* Рекурсивная функция построяния дерева */
/* На входе - обрабатываемая строка (возможно без 0-маркера), количество символов в строке */
struct element *build(char str[], int count)
{
struct element *el = (struct element *)malloc(sizeof(struct element)); /* Создаем новый элемент и выделяем под него память */
int n = findLastOperation(str, count); /* Ищем операцию с минимальным приоритетом - по ней будем производить разбивку */
if(n == -1) /* Если операция не найдена - значит переданная строка это просто число */
{
el->operation = 0; /* Операции нет - следовательно записываем в код операции 0 */
el->number = stringtoi(str, count); /* Записываем число */
} else /* Если операция найдена - нужно производить дальнейшую разбивку */
{
el->operation = str[n]; /* Записываем в код операции код найденного символа операции */
el->left = build(str, n); /* Вызываем функцию построения левого поддерева из левой части строки */
el->right = build(str + n + 1, count - n - 1); /* Вызываем функцию построения правого поддерева из правой части строки */
}
return el; /* Возвращаем получившийся результат */
}
/* Рекурсивная функция для вывода бинарного дерева на экран */
/* На входе - указатель на начало поддерева, смещение при печати */
void printTree(struct element *el, int n)
{
int i;
for(i = 0; i < n; i++) /* Печатаем пробелы для смещения*/
putchar(' ');
putchar('|');
if(el->operation == 0) /* Если код операции не записан - значит это просто число, выводим его */
{
printf("%d\n", el->number);
} else /* Если код операции записан - значит, выводим этот код на экран и запускаем обработку левого
и правого поддеревьев с большим смещением чем текущее */
{
printf("%c\n", el->operation);
printTree(el->left, n + 1);
printTree(el->right, n + 1);
}
}
int main()
{
char str[] = "(2+3)*4"; /* Задаем обрабатываемую строку, обязательно без пробелов*/
struct element *tree = build(str, strlen(str)); /* Строим дерево по заданной строке */
printTree(tree, 0); /* Выводим дерево на экран */
return 0;
}
P.S. я там по ходу дела одно исправление сделал - что бы если что прога могла и вложенные скобки обрабатывать, а именно в двух местах заменил if на while (оба раза - в функции stringtoi). |
