Помогите пожалуйста формулами для преобразования алгебраических выражений из инфиксных форм в постфиксные и префиксные с предусмотрением вхождения выражений с различными приоритетами и скобками.
Отслеживать
задан 21 мая 2017 в 19:20
850 3 3 золотых знака 18 18 серебряных знаков 37 37 бронзовых знаков
польская запись?) алгоритм на википедии есть
21 мая 2017 в 19:31
Сам когда-то писал калькулятор. Советую почитать про польскую запись/нотацию. Алгоритм Дейкстры для перевода в польскую нотацию.
9 июл 2017 в 17:53
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Там есть подробное описание, а по первой ссылке доступен пример на java.
- Имеем на входе формулу в инфиксной форме: a+b/(c-d);
- Перепишем формулу справа налево: (d-c)/b+a;
- Воспользуемся алгоритмом постфиксной трансляции, получим: dc-b/a+;
- Полученную формулу перепишем справа налево, получим формулу в префиксной записи: +a/b-cd.
Отслеживать
ответ дан 21 мая 2017 в 19:35
1,526 1 1 золотой знак 11 11 серебряных знаков 26 26 бронзовых знаков
10 класс профиль Префиксная и постфиксная формы записи выражений
- java
- алгоритм
- любой-язык
-
Важное на Мете
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Источник: ru.stackoverflow.com
Написать программу, которая преобразует выражение из инфиксной формы в префиксную — C#
Используя класс Stack написать программу, которая преобразует выражение из инфиксной формы в префиксную. т.е. по такому принципу:
Код к задаче: «Написать программу, которая преобразует выражение из инфиксной формы в префиксную»
Листинг программы
class Program < static void Main(string[] args) < // string infix = «3 ^ 4 + ( 11 — ( 3 * 2 ) ) / 2»; string infix = «3 + 2»; string[] tokens = infix.Split(‘ ‘); Stacks = new Stack(); List outputList = new List(); int n; foreach (string c in tokens) < if (int.TryParse(c.ToString(), out n)) < outputList.Add(c); >if (c == «(«) < s.Push(c); >if (c == «)») < while (s.Count != 0 s.Peek() != «(«) < outputList.Add(s.Pop()); >s.Pop(); > if (isOperator(c) == true) < while (s.Count != 0 Priority(s.Peek()) >= Priority(c)) < outputList.Add(s.Pop()); >s.Push(c); > > while (s.Count != 0)//if any operators remain in the stack, pop all outputList.Add(s.Pop()); >for (int i = 0; i < outputList.Count; i++) < Console.Write(«», outputList[i]); > Console.ReadLine(); > static int Priority(string c) < if (c == «^») < return 3; >else if (c == «*» || c == «/») < return 2; >else if (c == «+» || c == «-«) < return 1; >else < return 0; >> static bool isOperator(string c) < if (c == «+» || c == «-» || c == «*» || c == «/» || c == «^») < return true; >else < return false; >> >
Источник: studassistent.ru
Записать в префиксной форме выражение a+5∙b-(7-c)∙d+6∙e
Преобразование условного уравнения из инфиксной в префиксную нотацию
В нашем приложении мы разрешаем пользователям писать конкретные условия, и мы разрешаем им выражать условия с использованием таких обозначений:
(1 and 2 and 3 or 4)
Где каждое числовое число соответствует одному конкретному правилу/условию. Теперь проблема в том, как ее преобразовать, так что конечный результат выглядит примерно так:
Еще один пример:
(1 or 2 or 3 and 4)
Я написал 50 строк в токенизаторе, которые успешно подписали инструкцию в токенах и проверяли с помощью алгоритма stack/peek, а токены выглядят следующим образом:
[«(«, «1», «and», «2», «and», «3», «or», «4», «)»]
- Смарт-дизайн математического анализатора
- Добавьте отсутствующие левые круглые скобки в уравнение
- Синтаксический анализатор (выражение) с приоритетом?
- Инфикс к постфиксной нотации
- Алгоритм Дэйкстра Шунтингового дворца
- Инфикс и постфиксный алгоритм
ИЗМЕНИТЬ
Кроме того, пользователь может указать любое количество скобок, если они настаивают, например:
((1 or 3) and (2 or 4) or 5)
Поэтому он получает перевод:
РЕДАКТИРОВАТЬ 2
Я вычислил алгоритм. Опубликован как ответ ниже. Спасибо за помощь!
Lionel Chan 08 янв. 2014, в 04:44
Поделиться
zerkms 08 янв. 2014, в 03:17
Lionel Chan 08 янв.
2014, в 03:19
PS: я думаю, что у вашего AST для второго случая нет второго $or токена. Это должно выглядеть так: sketchia.com/draw_G2HXgRv.html PPS: сумасшедшие навыки рисования, которые я знаю)
zerkms 08 янв. 2014, в 03:19
Lionel Chan 08 янв. 2014, в 03:28
Я думаю, что это гораздо проще построить. Если вы запишите свой синтаксис, используя BNF, вы обнаружите, что мой рисунок соответствует ему.
zerkms 08 янв. 2014, в 03:33
Благодарю. Позвольте мне немного переварить это. Я забыл большинство алгоритмов учиться в школе 🙂
Lionel Chan 08 янв.
2014, в 03:35
Но, во-первых, они могут написать любое количество скобок, чтобы они выглядели сложнее ((1 or 3) and (2 or 4) or 5)
Lionel Chan 08 янв. 2014, в 03:37
Спасибо за попытку. Я разобрался с решением! 🙂 Спасибо!
Lionel Chan 09 янв. 2014, в 15:33
Показать ещё 6 комментариев
Поделиться:
3 ответа
Лучший ответ
Спасибо за ребята, ребята, по крайней мере, я вышел с моим собственным решением. Поскольку это мой первый раз, когда я занимаюсь математическим анализом уравнений, прошу прощения, если я сделал это неправильно или неэффективно или помог мне определить ошибку:
В основном, вот шаги, которые я сделал:
- Перед синтаксическим разбором всегда проверяйте шаблон. Бросьте ошибку, если что-то не так.
- После проверки мы делаем нотацию в префиксном преобразовании нотации. Этот шаг требует «и» имеет приоритет над «или».
- Обратный шаблон
- Сделайте infix для преобразования нотации Postfix. Я немой, я узнаю из этого
- Сделайте обратное снова
- Инфикс к префиксу должен быть выполнен на этом этапе
- A node всегда имеют и максимум две ветки
- Пройдите вниз, пока не достигнете полных листьев.
Рабочий код, как показано ниже:
Lionel Chan 09 янв. 2014, в 16:33
Поделиться
Это проще всего сделать с помощью двухэтапного процесса. 1) Преобразовать в дерево синтаксиса. 2) Преобразование дерева синтаксиса в префиксную нотацию.
Дерево синтаксиса в основном такое же, как ваша префиксная нотация, только что построенная с использованием структур данных вашего языка программирования.
Стандартный метод создания дерева синтаксиса — использовать генератор парсера LALR, который доступен для большинства языков. Анализаторы LALR бывают быстрыми, мощными и выразительными. Генератор парсеров LALR принимает файл .y в качестве входных данных и выводит файл исходного кода для синтаксического анализатора на выбранном вами языке программирования. Таким образом, вы запускаете генератор парсер LALR один раз для генерации вашего синтаксического анализатора.
(Все программисты должны научиться использовать генераторы парсеров:). Также разумно использовать стандартный токенизатор, в то время как я предполагаю, что вы написали свой собственный:).)
Ниже представлен файл .y для создания LALR-парсера для вашего мини-языка. Запуск этого .y файла, хотя генератор парсеров LALR выведет источник для парсера LALR, который принимает токены в качестве входных данных и выводит дерево синтаксического анализа (в переменной $root_tree). Вы должны определить структуру данных parsetree_binaryop вручную в другом месте.
%left AND. %left OR. start ::= expr(e). < $root_tree = e; >expr(r) ::= expr(e1) AND expr(e2). < r = new parsetree_binaryop(e1, OP_AND, e2); >expr(r) ::= expr(e1) OR expr(e2). < r = new parsetree_binaryop(e1, OP_OR, e2); >expr(r) ::= LPAR expr(e) RPAR.
«% left AND» означает, что AND лево-ассоциативный (мы тоже могли бы выбрали право, не имеет значения для AND и OR).
То, что «% left AND» упоминается до того, как «% left OR» означает, что AND привязывается более жестко, чем OR, и поэтому сгенерированный синтаксический анализатор сделает правильные вещи.
Когда у вас есть синтаксическое дерево, которое дает синтаксический анализатор, создание текстового представления легко.
Изменить: похоже, это генератор парсеров LALR, который выводит парсер в JavaScript: http://sourceforge.net/projects/jscc/
Thue 08 янв. 2014, в 05:25
Поделиться
«Также разумно использовать стандартный токенизатор, хотя я предполагаю, что вы написали свой собственный» — дело в том, что js серьезно сосет в области синтаксического анализа. Когда я искал — я не нашел ничего приличного.
zerkms 08 янв. 2014, в 04:00
Должен ли написать свой собственный парсер тогда? 🙁 Дай мне проверить.. 🙂
Lionel Chan 08 янв. 2014, в 04:03
Вы имеете в виду «должен написать мой собственный генератор парсера»? Вероятно, у вас нет, sourceforge.net/projects/jscc кажется многообещающим.
Thue 08 янв. 2014, в 05:29
Спасибо всем за усилия. Я написал свое собственное решение .. 🙂
Lionel Chan 09 янв.
2014, в 15:25
Показать ещё 2 комментария
Сначала определите семантику. В первом примере вы дали интерпретацию (1 and 2 and 3) or 4 , но она также может быть 1 and 2 and (3 or 4) так:
Предположим, что and имеет более высокий приоритет. Затем просто перейдите в список, соедините все термины с помощью and . Затем присоедините все остальные к or .
Łukasz Kidziński 08 янв. 2014, в 11:39
Поделиться
Спасибо, но здесь я не оцениваю уравнение, поскольку у меня уже есть готовый код на стороне сервера, выполняющий оценку. Мне нужно преобразование, и я думаю, что я каким-то образом понял идею префикса infix->. Похоже, префикс может решить проблему. Я опубликую решение здесь, как только я закончу с ним.
Источник: overcoder.net