Используя стек, определить функцию, которая переводит выражение в префиксную форму

@sanchoflat · Регистрация: 05.11.2011

Author24 — интернет-сервис помощи студентам

Есть задание - Используя стек, определить функцию, которая переводит выражение, записанное в обычной (инфиксной) форме в префиксную форму. Предусмотреть ввод выражения с клавиатуры и из текстового файла.
В принципе проблем нету, но такой вопрос - как мне проходиться по каждому символу по порядку?
Вариант как запихнуть каждый символ в ячейку массива, но не катит так. Или используя string искать в цикле нужные элементы: скобки, символы..?

@Герц · 20.10.2012, 12:51

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

silent_1991 · 24.10.2012, 11:20

sanchoflat, в дополнение к предыдущему ответу, посмотрите в сторону автоматных анализаторов; это только звучит страшно, а реализуется через обычный switch-case, надо только чуть-чуть включить мозг и составить автомат для вашего языка. Он будет простым, на вскидку 4 состояния.

@sanchoflat · 24.10.2012, 17:03 **[ТС]**

честно не очень понимаю что это такое вообще. Разве нельзя просто пройтись по элементам string'а по очереди?

@Герц · 24.10.2012, 17:09

Ну опиши как ты это собрался делать таким образом, что ли.

silent_1991 · 25.10.2012, 12:13

sanchoflat, автоматный анализатор и будет проходить по ним по-очереди. Просто у него есть формальное определение, его надо составить на бумажке, и тогда по нему программу написать не составит никакого труда. Ну а на счёт "не очень понимаю"... Вы искали?

@sanchoflat · 25.10.2012, 15:53 **[ТС]**

silent_1991, первым делом загуглил, но статья на википедии и подобных сайтах об автоматном анализаторе не дала более конкретных знаний о том, как реализовать в программе.
В принципе выкрутился через array char'ов. Ими и оперирую пока что.

@sanchoflat · 26.10.2012, 18:58 **[ТС]**

Возникла проблема - делаю по алгоритму:
1. раскидываем знаки и операнды в разные стеки. если в выражении встречаем ')'
то отыскиваем в стеке соответствущую левую скобку и все что выше '(' выталкиваем в стек с операндами. ( а после этого мы удаляем '(' ?)
2. Дальше проходим по выражению и если мы встречаем операнд, который по приоритету меньше чем верхний элемент стека или не является '(' то выталкиваем элементы из стека со знаками в стек с операндами, пока не встретим '(' или дно стека.

C++

array <wchar_t> ^mas;
            Stack^ myStackX = gcnew Stack;
            Stack^ myStackY = gcnew Stack;
            int j = 0;
                for (int i = 0; i < n; i++)
                    {
                        if ( out[i] >='A' && out[i]<='Z')
                            {
                                myStackX->Push(Convert::ToChar(out[i]));
                            }
                        
                        else if ( out[i] =='+' || out[i] =='-' || out[i] =='*' || out[i] =='/' || out[i] == '^' || out[i] == '(')
                            {
                                myStackY->Push(Convert::ToChar(out[i]));    
                            }
                        else if ( out[i] == ')' )
                            {
                                while ( myStackY->Peek() != '(' );
                                    {
                                        /*if ( myStackY->Peek() == '(')
                                            myStackY->Pop();
                                        else
                                            {*/
                                                myStackX->Push(maStackY->Peek());
                                                myStackY->Pop();
                    MessageBox::Show(Convert::ToString(myStackY->Peek()));
                                        //  }
                                    }
                                
                            }
                    //  else 
                    //      MessageBox::Show("Некорректная запись!");
                    }

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

Добавлено через 1 час 32 минуты
собственно поправил

C++

void algoritm(int n, array <wchar_t> ^out)
        {
            array <wchar_t> ^mas;
            Stack^ myStackX = gcnew Stack;
            Stack^ myStackY = gcnew Stack;
            int j = 0;
                for (int i = 0; i < n; i++)
                    {
                        if ( out[i] >='A' && out[i]<='Z')
                            {
                                myStackX->Push(out[i]);
                            }
                        
                        else if ( out[i] =='+' || out[i] =='-' || out[i] =='*' || out[i] =='/' || out[i] == '^' || out[i] == '(')
                            {
                                myStackY->Push(out[i]);             
                            }
                        else if ( out[i] == ')' )
                            {
                                do
                                {
                                        if ( Convert::ToChar(myStackY->Peek()) == '(')
                                            {
                                                myStackY->Pop();
                                                break;
                                            }
                                        else
                                            {
                                                myStackX->Push(myStackY->Peek());
                                                myStackY->Pop();    
                                        }
                                }
                                while ( Convert::ToChar(myStackY->Peek()) != '(' );
                                myStackY->Pop();
                            }

но как быть дальше с проверкой - если следующий знак по приоритету меньше чем верх стека, то перекидываем в стек с операндами. Я присваиваю приоритеты операциям, но не пойму - как мне все это реализовать в своем одном цикле?

@sanchoflat 5 / 7 / 3 Регистрация: 05.11.2011 Сообщений: 97
		1
	Используя стек, определить функцию, которая переводит выражение в префиксную форму 20.10.2012, 12:49. Показов 1361. Ответов 7 Метки нет (Все метки) Есть задание - Используя стек, определить функцию, которая переводит выражение, записанное в обычной (инфиксной) форме в префиксную форму. Предусмотреть ввод выражения с клавиатуры и из текстового файла. В принципе проблем нету, но такой вопрос - как мне проходиться по каждому символу по порядку? Вариант как запихнуть каждый символ в ячейку массива, но не катит так. Или используя string искать в цикле нужные элементы: скобки, символы..? 0

@Герц 545 / 344 / 12 Регистрация: 05.11.2010 Сообщений: 1,076 Записей в блоге: 1
	20.10.2012, 12:51	2
	написать простенький лексический анализатор, вычленяющий из строки следующий токен и возвращающий его тебе. 0

silent_1991 5056 / 3116 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	24.10.2012, 11:20	3
	sanchoflat, в дополнение к предыдущему ответу, посмотрите в сторону автоматных анализаторов; это только звучит страшно, а реализуется через обычный switch-case, надо только чуть-чуть включить мозг и составить автомат для вашего языка. Он будет простым, на вскидку 4 состояния. 0

@sanchoflat 5 / 7 / 3 Регистрация: 05.11.2011 Сообщений: 97
	24.10.2012, 17:03 [ТС]	4
	честно не очень понимаю что это такое вообще. Разве нельзя просто пройтись по элементам string'а по очереди? 0

@Герц 545 / 344 / 12 Регистрация: 05.11.2010 Сообщений: 1,076 Записей в блоге: 1
	24.10.2012, 17:09	5
	Ну опиши как ты это собрался делать таким образом, что ли. 0

silent_1991 5056 / 3116 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	25.10.2012, 12:13	6
	sanchoflat, автоматный анализатор и будет проходить по ним по-очереди. Просто у него есть формальное определение, его надо составить на бумажке, и тогда по нему программу написать не составит никакого труда. Ну а на счёт "не очень понимаю"... Вы искали? 0

@sanchoflat 5 / 7 / 3 Регистрация: 05.11.2011 Сообщений: 97
	25.10.2012, 15:53 [ТС]	7
	silent_1991, первым делом загуглил, но статья на википедии и подобных сайтах об автоматном анализаторе не дала более конкретных знаний о том, как реализовать в программе. В принципе выкрутился через array char'ов. Ими и оперирую пока что. 0

	26.10.2012, 18:58