Содержание урока
Вычисление арифметических выражений
Вычисление арифметических выражений
Один из способов вычисления арифметических выражений основан на использовании дерева. Сначала выражение, записанное в линейном виде (в одну строку), нужно «разобрать» и построить соответствующее ему дерево. Затем в результате прохода по этому дереву от листьев к корню вычисляется результат.
Нужно сначала найти последнюю операцию, просматривая выражение слева направо. Здесь последняя операция — это второе вычитание, оно оказывается в корне дерева (рис. 6.15).
Как выполнить этот поиск в программе? Известно, что операции выполняются в порядке приоритета (старшинства): сначала операции с более высоким приоритетом (слева направо), потом — с более низким (также слева направо). Отсюда следует важный вывод.
В корень дерева нужно поместить последнюю из операций с наименьшим приоритетом.
Теперь нужно построить таким же способом левое и правое поддеревья (рис. 6.16).
Левое поддерево требует ещё одного шага (рис. 6.17).
Эта процедура рекурсивная, её можно записать в виде псевдокода:
Рекурсия заканчивается, когда в оставшейся части строки нет ни одной операции, значит, там находится число (это лист дерева).
Теперь вычислим выражение по дереву. Если в корне находится знак операции, её нужно применить к результатам вычисления поддеревьев:
Снова получился рекурсивный алгоритм.
Возможен особый случай (на нём заканчивается рекурсия), когда корень дерева содержит число (т. е. это лист). Это число и будет результатом вычисления выражения.
Следующая страница 
Использование связанных структур
Cкачать материалы урока
Источник
Урок 4
Структура информации (простые структуры). Деревья. Графы
§4. Структура информации
Содержание урока
Задачи
Задачи
1. Определите выражения, соответствующие каждому из деревьев, в «нормальном» виде со скобками (эту форму называют инфиксной — операция записывается между данными). Постройте для каждого из них постфиксную форму.
2. Постройте деревья, соответствующие следующим арифметическим выражениям. Запишите эти выражения в префиксной и постфиксной формах:
3. Вычислите выражения, записанные в постфиксной форме:
Запишите каждое из них в инфиксной и в префиксной формах и постройте соответствующее дерево. Единственно ли такое дерево? В этом дереве назовите корень, листья и промежуточные вершины.
4. Нарисуйте граф, в котором 5 вершин и три компоненты связности. Постройте его матрицу смежности.
5. Структурируйте следующую информацию разными способами: «Между посёлками Верхний и Нижний есть просёлочная дорога длиной 10 км. Село Сергеево соединяется двумя асфальтовыми шоссе с Нижним (22 км) и Верхним (16 км). В село Солнечное можно доехать только из Сергеева по грунтовой дороге (5 км)». Можно ли сказать точно, как расположены эти пункты?
6. Для графа, полученного в предыдущей задаче, постройте матрицу смежности, список смежности, весовую матрицу. Является ли этот граф деревом?
7. Постройте матрицы смежности и весовые матрицы графов:
8. Постройте графы, соответствующие матрицам смежности.
9. Постройте графы, соответствующие весовым матрицам.
10. Стоимость перевозок между пунктами, которые для краткости обозначены буквами А, В, С, D и Е, задаётся таблицей (весовой матрицей графа). Нужно перевезти груз из пункта А в пункт В. Для каждого из четырёх вариантов определите оптимальный маршрут и полную стоимость перевозки.
11. Постройте орграфы, соответствующие весовым матрицам.
Для каждого из орграфов найдите количество различных маршрутов из вершины А во все остальные вершины.
Следующая страница Практическая работа № 1 «Оформление документа»
Cкачать материалы урока
Источник
Дерево выражений
Дерево выражений — это двоичное дерево, в котором каждый внутренний узел соответствует оператору, а каждый конечный узел соответствует операнду, поэтому, например, дерево выражений для 3 + ((5 + 9) * 2) будет иметь вид:
Обход по порядку в дереве выражений создает инфиксную версию заданного постфиксного выражения (то же самое, что и при обходе по предварительному заказу — префиксное выражение)
Оценка выражения, представленного деревом выражений:
Построение дерева выражений:
Теперь для построения дерева выражений мы используем стек. Мы перебираем входное выражение и делаем следующее для каждого символа.
1) Если символ является операндом, поместите его в стек
2) Если символ является оператором, извлеките два значения из стека, сделайте их дочерними и снова нажмите текущий узел.
В конце корнем дерева выражений будет только элемент стека.
Ниже приведена реализация:
// C ++ программа для дерева выражений
#include
using namespace std;
// Узел дерева выражений
// Утилита для проверки, если ‘c’
// оператор
bool isOperator( char c)
// Сервисная функция для выполнения обхода inorder
void inorder(et *t)
// Вспомогательная функция для создания нового узла
et* newNode( int v)
et *temp = new et;
temp->left = temp->right = NULL;
// Возвращает корень построенного дерева для данного
// постфиксное выражение
et* constructTree( char postfix[])
// Обход каждого символа
for ( int i=0; i strlen (postfix); i++)
// Если операнд, просто вставить в стек
// Вставляем два верхних узла
t1 = st.top(); // Магазин сверху
st.pop(); // Удалить верх
// сделать их детьми
// Добавить это подвыражение в стек
// корнем выражения будет только элемент
// Программа драйвера для тестирования выше
char postfix[] = «ab+ef*g*-» ;
et* r = constructTree(postfix);
printf ( «infix expression is \n» );
// Java-программа для построения дерева выражений
// Java-программа для дерева выражений
Node left, right;
left = right = null ;
// Утилита для проверки, если ‘c’
boolean isOperator( char c) <
// Сервисная функция для выполнения обхода inorder
void inorder(Node t) <
// Возвращает корень построенного дерева для данного
Node constructTree( char postfix[]) <
Stack st = new Stack();
// Обход каждого символа
for ( int i = 0 ; i
// Если операнд, просто вставить в стек
t = new Node(postfix[i]);
t = new Node(postfix[i]);
// Вставляем два верхних узла
t1 = st.pop(); // Удалить верх
// сделать их детьми
// System.out.println (t1 + «» + t2);
// Добавить это подвыражение в стек
// корнем выражения будет только элемент
public static void main(String args[]) <
ExpressionTree et = new ExpressionTree();
String postfix = «ab+ef*g*-» ;
char [] charArray = postfix.toCharArray();
Node root = et.constructTree(charArray);
System.out.println( «infix expression is» );
// Этот код предоставлен Mayank Jaiswal
# Python-программа для дерева выражений
# Узел дерева выражений
# Конструктор для создания узла
# Полезная функция для проверки, если ‘c’
# является оператором
if (c = = ‘+’ or c = = ‘-‘ or c = = ‘*’
# Полезная функция для обхода inorder
if t is not None :
# Возвращает корень построенного дерева для
# данное постфиксное выражение
# Обход каждого символа входного выражения
for char in postfix :
# если операнд, просто вставьте в стек
if not isOperator(char):
# Поп два верхних узла
# сделать их детьми
# Добавить это подвыражение в стек
# Только элемент будет корнем дерева выражений
# Программа драйвера для тестирования выше
print «Infix expression is»
// C # программа для построения дерева выражений
public class Node
public char value;
public Node left, right;
public Node( char item)
left = right = null ;
// Утилита для проверки, если ‘c’
Boolean isOperator( char c)
// Сервисная функция для выполнения обхода inorder
void inorder(Node t)
// Возвращает корень построенного дерева для данного
Node constructTree( char []postfix)
Stack st = new Stack();
// Обход каждого символа
for ( int i = 0; i
// Если операнд, просто вставить в стек
t = new Node(postfix[i]);
t = new Node(postfix[i]);
// Вставляем два верхних узла
t1 = (Node)st.Pop(); // Удалить верх
// сделать их детьми
// System.out.println (t1 + «» + t2);
// Добавить это подвыражение в стек
// только элемент будет корнем
public static void Main(String []args)
ExpressionTree et = new ExpressionTree();
String postfix = «ab+ef*g*-» ;
char [] charArray = postfix.ToCharArray();
Node root = et.constructTree(charArray);
Console.WriteLine( «infix expression is» );
// Этот код предоставлен Арнабом Кунду
Источник