бинарное дерево | C++ для приматов

Задача

Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z — w) — арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w — * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.

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

push: число кладется на верх стека.
pop: число снимается с вершины стека.

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

a := pop();

b := pop();

push(b O a);

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

Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push иpop, но их смысл немного другой:

push: число вставляется в конец очереди.
pop: из начала очереди извлекается число.

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

Пояснения к решению

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

Просматриваем строку слева направо
Если встречаем переменную, помещаем её в конец стека/очереди
Если встречаем символ оператора * , то выполняем следующие действия: снимаем со стека a, снимаем со стека b и кладём на стек b * a.

По условию задачи, мы должны обрабатывать строки, используя вместо стека очередь, поэтому описанные выше действия примут следующий вид: снимаем с очереди a, снимаем с очереди b и кладём в конец очереди b * a.

Постфиксную запись, рассчитанную на обработку посредством стека, будем называть s-постфиксной, а рассчитанную на обработку очередью — q-постфиксной.

Две записи «вычислятся одинаково» в том и только в том случае, когда соответствующие им деревья синтаксического разбора (англ.: parse tree, далее — ДСР) одинаковы. Идея приведённого ниже алгоритма состоит примерно в следующем: на основе s-постфиксной записи строим ДСР, обходя которое специальным образом, получаем q-постфиксную запись. Нужно обходить дерево по уровням справа налево (под уровнем дерева подразумевается множество всех вершин дерева, равноудалённых от корня; уровни дерева естественным образом нумеруются: корень расположен на уровне 0 и так далее). В приведённом ниже коде функция get_levels генерирует уровни ДСР на основе s-постфиксной нотации в виде вектора строк, k-ая компонента которого соответствует k-му уровню ДСР заданной строки, вершины которого (если таковые имеются) перечислены справа налево. Поскольку у ДСР может быть не больше уровней, чем символов в строке, то создаём вектор как раз с таким числом компонент и инициализируем его компоненты пустыми строками.

Корректность функции get_levels можно доказать индукцией по длине строки, отметим, что если строка содержит более одного элемента, то она имеет вид ФGО, где Ф и G — правильные строки, О — символ оператора. Запустить рекурсивно функцию с предпоследней позиции — всё равно, что применить её к строке G. ДСР этой строки является левым поддеревом для ДСР исходной строки и k-ый уровень этого дерева является (k+1)-ым уровнем ДСР исходной строки (именно поэтому вызываем функцию с параметром depth на 1 больше). По индукционному предположению, дойдя до начала строки G, функция корректно «расставит» уровни ДСР этой строки (с учётом + 1) и завершит свою работу. Аналогично будут правильно расставлены уровни ДСР строки Ф, которое является правым поддеревом исходной строки. Таким образом, все вершины ДСР исходной строки будут правильно расставлены, а поскольку рекурсия вызывается сначала для левого, а потом для правого её поддерева, то и перечислены вершины на каждом уровне будут справа налево.

Код на С++

Ссылка на программу в ideone.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем
 index - текущий символ в строке Expr
 depth - текущий уровень дерева разбора
 Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {
	Answer[depth] += Expr[index];
	index--;
	if (isupper(Expr[index+1])) {
		get_levels(Expr, index, depth + 1, Answer);
		get_levels(Expr, index, depth + 1, Answer);
	}
}


int main() {
	int n, index;
	cin >> n;
	string Expr;
	for (int k = 0; k < n; k++) {
		cin >> Expr;						
		vector<string> Answer(Expr.size(), "");
		index = Expr.size() - 1;
		get_levels(Expr, index, 0, Answer);
		for (int k = Expr.size() - 1; k >= 0; k--)
			cout << Answer[k];
		cout << endl;
	}
	return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем

index - текущий символ в строке Expr

depth - текущий уровень дерева разбора

Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {

Answer[depth] += Expr[index];

index--;

if (isupper(Expr[index+1])) {

get_levels(Expr, index, depth + 1, Answer);

}

int main() {

int n, index;

cin >> n;

string Expr;

for (int k = 0; k < n; k++) {

cin >> Expr;

vector<string> Answer(Expr.size(), "");

index = Expr.size() - 1;

get_levels(Expr, index, 0, Answer);

for (int k = Expr.size() - 1; k >= 0; k--)

cout << Answer[k];

cout << endl;

}

return 0;

}

Код на Java

Ссылка на программу в ideone.

import java.util.*;
import java.lang.*;
import java.io.*;

class Index {
	int in;
	public Index(int a) {
		in = a;
	}
}

class Main
{
	public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {
		Answer[depth] += Expr[index.in];
		index.in--;
		if (Character.isUpperCase(Expr[index.in + 1])) {
			get_levels(Expr, index, depth + 1, Answer);
			get_levels(Expr, index, depth + 1, Answer);
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String str = in.nextLine();

		for (int k = 0; k < n; k++) {
			str = in.nextLine();
			char[] Expr = str.toCharArray();
			String[] Answer = new String[Expr.length];
			Arrays.fill(Answer, "");
			Index index = new Index(Expr.length - 1);
			get_levels(Expr, index, 0, Answer);
			for (int j = Expr.length - 1; j >= 0; j--)
				System.out.print(Answer[j]);
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Index {

int in;

public Index(int a) {

in = a;

}

class Main

{

public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {

Answer[depth] += Expr[index.in];

index.in--;

if (Character.isUpperCase(Expr[index.in + 1])) {

get_levels(Expr, index, depth + 1, Answer);

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String str = in.nextLine();

for (int k = 0; k < n; k++) {

str = in.nextLine();

char[] Expr = str.toCharArray();

String[] Answer = new String[Expr.length];

Arrays.fill(Answer, "");

Index index = new Index(Expr.length - 1);

get_levels(Expr, index, 0, Answer);

for (int j = Expr.length - 1; j >= 0; j--)

System.out.print(Answer[j]);

System.out.println();

}

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: бинарное дерево

e-olimp 3837. Выражения

Related Images: