Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
sanchoflat
4 / 6 / 1
Регистрация: 05.11.2011
Сообщений: 97
20.10.2012, 12:49     Используя стек, определить функцию, которая переводит выражение в префиксную форму #1
Есть задание - Используя стек, определить функцию, которая переводит выражение, записанное в обычной (инфиксной) форме в префиксную форму. Предусмотреть ввод выражения с клавиатуры и из текстового файла.
В принципе проблем нету, но такой вопрос - как мне проходиться по каждому символу по порядку?
Вариант как запихнуть каждый символ в ячейку массива, но не катит так. Или используя string искать в цикле нужные элементы: скобки, символы..?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2012, 12:49     Используя стек, определить функцию, которая переводит выражение в префиксную форму
Посмотрите здесь:

Написать функцию, которая переводит введенную пользователем маленькую букву в большую C++
C++ Опишите функцию int vms(int Vkmh), которая переводит значение Vkmh из км/ч в м/с
Описать функцию int vms(int Vkmh), которая переводит значение Vkmh из км/ч в м/с C++
C++ Используя стек, определить, является ли введённая с клавиатуры строка палиндромом
Используя стек, определить, является ли введённая с клавиатуры строка палиндромом. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
20.10.2012, 12:51     Используя стек, определить функцию, которая переводит выражение в префиксную форму #2
написать простенький лексический анализатор, вычленяющий из строки следующий токен и возвращающий его тебе.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
24.10.2012, 11:20     Используя стек, определить функцию, которая переводит выражение в префиксную форму #3
sanchoflat, в дополнение к предыдущему ответу, посмотрите в сторону автоматных анализаторов; это только звучит страшно, а реализуется через обычный switch-case, надо только чуть-чуть включить мозг и составить автомат для вашего языка. Он будет простым, на вскидку 4 состояния.
sanchoflat
4 / 6 / 1
Регистрация: 05.11.2011
Сообщений: 97
24.10.2012, 17:03  [ТС]     Используя стек, определить функцию, которая переводит выражение в префиксную форму #4
честно не очень понимаю что это такое вообще. Разве нельзя просто пройтись по элементам string'а по очереди?
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
24.10.2012, 17:09     Используя стек, определить функцию, которая переводит выражение в префиксную форму #5
Ну опиши как ты это собрался делать таким образом, что ли.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
25.10.2012, 12:13     Используя стек, определить функцию, которая переводит выражение в префиксную форму #6
sanchoflat, автоматный анализатор и будет проходить по ним по-очереди. Просто у него есть формальное определение, его надо составить на бумажке, и тогда по нему программу написать не составит никакого труда. Ну а на счёт "не очень понимаю"... Вы искали?
sanchoflat
4 / 6 / 1
Регистрация: 05.11.2011
Сообщений: 97
25.10.2012, 15:53  [ТС]     Используя стек, определить функцию, которая переводит выражение в префиксную форму #7
silent_1991, первым делом загуглил, но статья на википедии и подобных сайтах об автоматном анализаторе не дала более конкретных знаний о том, как реализовать в программе.
В принципе выкрутился через array char'ов. Ими и оперирую пока что.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.10.2012, 18:58     Используя стек, определить функцию, которая переводит выражение в префиксную форму
Еще ссылки по теме:

Определите функцию, которая возвращает площадь треугольника, используя формулу C++
Написать функцию, которая переводит число в другую систему счисления C++
C++ Преобразовать выражение используя функцию abs

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
sanchoflat
4 / 6 / 1
Регистрация: 05.11.2011
Сообщений: 97
26.10.2012, 18:58  [ТС]     Используя стек, определить функцию, которая переводит выражение в префиксную форму #8
Возникла проблема - делаю по алгоритму:
1. раскидываем знаки и операнды в разные стеки. если в выражении встречаем ')'
то отыскиваем в стеке соответствущую левую скобку и все что выше '(' выталкиваем в стек с операндами. ( а после этого мы удаляем '(' ?)
2. Дальше проходим по выражению и если мы встречаем операнд, который по приоритету меньше чем верхний элемент стека или не является '(' то выталкиваем элементы из стека со знаками в стек с операндами, пока не встретим '(' или дно стека.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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();
                            }
но как быть дальше с проверкой - если следующий знак по приоритету меньше чем верх стека, то перекидываем в стек с операндами. Я присваиваю приоритеты операциям, но не пойму - как мне все это реализовать в своем одном цикле?
Yandex
Объявления
26.10.2012, 18:58     Используя стек, определить функцию, которая переводит выражение в префиксную форму
Ответ Создать тему
Опции темы

Текущее время: 07:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru