Из постфиксной в инфиксную нотацию

Об обратной польской нотации(записи) на Хабре уже рассказывали ^[1]. Как известно вся сила ОПН в постфиксной записи математического выражения. О том как преобразовать привычную для нас инфиксную запись в постфиксную детально рассмотрено в статье выше, на Википедии ^[2] и даже приведена реализация на Ассемблере ^[3]. Но вот о том как провернуть обратное действие я статей не нашел.

Наверно, первый вопрос который вы зададите: «А зачем это нужно?». А представьте, что мы оптимизируем вводимое пользователем выражение и результат нам надо показать в инфиксной записи, а оптимизировать мы будем, конечно, с помощью ОПН.

Ну, теперь ближе к делу:

Словесное описание алгоритма:

1. Если читаем число, то заносим его в стек
2. Если читаем знак операции, то:
   • Берем 2 верхних элемента стека
   • Если в первом элементе приоритет операции меньше(и не равен 0), чем у рассматриваем операции, то берем первый элемент в скобки
   • Аналогично для 2-го элемента
   • Записываем в стек строку вида: 2-й элемент + знак операции + 1-й элемент

3. Если строка полностью пройдена, то результатом является значение вершины стека

Реализация на С++

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

// <--Структуры данных-->
enum optype {power = 3, devide = 2, multiply = 2, minus = 1, plus = 1, null=0}; // приоритеты операций

struct stack {
	char val[100]; // непосредственно значение элемента
	optype type; // приоритет операции, необходим для правильного расставления  скобок
	stack * next;
} *head;

// <--Функции работы со стеком-->
void push(char[], optype);
void push(stack *);
stack * pop();
// <--Функция выполняющая наш алгоритм-->
void fromRPN(char *, char *); // (RPN) Reverse polish notation

int main() {
	char infix[100], postfix[100]; // входная и выходная строка
	gets(infix);
	fromRPN(infix, postfix);
	printf("%sn", postfix);
	system("PAUSE");
	return 0;
}

void push(stack *t) {
	t->next = head;
	head = t;
}

void push(char str[], optype type) {
	stack *t;
	t = new stack;
	strcpy(t->val, str);
	t->type = type;
	t->next = head;
	head = t;
}

stack * pop() {
	stack *t;
	if(head == NULL) return NULL;
	t = head;
	head = t->next;
	return t;
}

void fromRPN(char * input, char * output) {
	char c, temp[100];
	int p_temp=0;
	stack *h1, *h2; // переменные для хранения первых двух элементов стека
	optype type;
	head = NULL;
	while(*input) { // пока есть символы строке
		c = (*input);
		if(c>='0' && c<='9' || c=='.') { //если текущий символ часть числа
			temp[p_temp++] = c; //то добавляем его во временную строку
			temp[p_temp] = '';
		} else if(c==' ') {
			if(p_temp!=0) {
				push(temp, null); // добавляем число в стек
				p_temp=0; }
			temp[0] = ''; // опустошаем временную строку
		} else if(c=='+' || c=='-'|| c=='*' || c=='/' || c=='^') { //если читаем знак операции
			h1 = pop(); // выталкиваем первый элемент
			h2 = pop(); // выталкиваем второй элемент
                        // находим приоритет операции
			if(c=='+') type = plus;
			else if(c=='-') type = minus;
			else if(c=='*') type = multiply;
			else if(c=='/') type = devide;
			else if(c=='^') type = power;
			if(h2->type!=null && h2->type<type) { // если приоритет для 1-го элемента меньше
				temp[0]='('; temp[1] = ''; // берем выражение в скобки
				h2->val[strlen(h2->val)+2] = '';
				h2->val[strlen(h2->val)+1] = c; // приписываем знак операции
				h2->val[strlen(h2->val)] = ')';
			} else {
				h2->val[strlen(h2->val)+1] = '';
				h2->val[strlen(h2->val)] = c;
			}
			strcat(temp, h2->val);
			if(h1->type!=null && h1->type<type) {  // если приоритет для 2-го элемента меньше
				strcat(temp, "(");
				h1->val[strlen(h1->val)+1] = '';
				h1->val[strlen(h1->val)] = ')'; // берем выражение в скобки
			}
			strcat(temp, h1->val);
			strcpy(h2->val, temp); // что бы не выделять память под новый элемент, копируем полученное выражение во второй элемент
			delete h1; // удаляем первый элемент
			h2->type = type; // устанавливаем новый приоритет операции
			push(h2); // добавляем новый элемент в стек
		}
		input++;
	}
	strcpy(output, (pop())->val); // копируем выражение из вершины стека в строку результата
}

Пример работы

Для примера возьмем преобразованное выражение из примера в статье с хабра:

Инфиксная: (8+2*5)/(1+3*2-4)
Постфиксная: 8 2 5 * + 1 3 2 * + 4 - /

Читаем "8"
Стек: {"8", null=0}

Читаем "8"
--Стек: {"8", null=0}

Читаем "2"
--Стек: {"2", null=0}, {"8", null=0}

Читаем "5"
--Стек: {5, null=0}, {"2", null=0}, {"8", null=0}

Читаем "*"
--Стек: {"2*5", multiply=2}, {"8", null=0}

Читаем "+"
--Стек: {"8+2*5", plus=1}

Читаем "1"
--Стек: {"1", null=0}, {"8+2*5", plus=1}

Читаем "3"
--Стек: {"3", null=0}, {"1", null=0}, {"8+2*5", plus=1}

Читаем "2"
--Стек: {"2", null=0}, {"3", null=0}, {"1", null=0}, {"8+2*5", plus=1}

Читаем "*"
--Стек: {"3*2", multiply=2}, {"1", null=0}, {"8+2*5", plus=1}

Читаем "+"
--Стек: {"1+3*2", plus=1}, {"8+2*5", plus=1}

Читаем "4"
--Стек: {"4", null=0}, {"1+3*2", plus=1}, {"8+2*5", plus=1}

Читаем "-"
--Стек: {"1+3*2-4", minus=1}, {"8+2*5", plus=1}

Читаем "/"
//в обеих элементах приоритет ниже, поэтому берем их в скобки
--Стек: {"(8+2*5)/(1+3*2-4)", devide=2}

Результат: (8+2*5)/(1+3*2-4)

Автор: gorz