calculator operator precedence

[Mayor]

calculator operator precedence

хочу для тренировки написать на с++, безо всякого встраивания интепретируемых языков, интерпретируемый консольный калькулятор

читает символы с клавиатуры, как только получает символ конца выражения выводит его результат на экран

операторы:
()
*\%
+-
= \\ определяет переменную, которую можно потом подставить в выражение
func_name(arg1,arg2, ...)=    \\ определяет функцию и ее аргументы,которую можно будет потом подставить в выражение

насколько необходимо приведение к польской\венгерской нотации?
как в общем может выглядеть алгоритм, который определяет превосходство операторов?
скорее всего тут потребуется структура типа дерево?
как можно обойти явноя задания деревьев для упрощения кода?

как можно описать конкретный пример работы алгоритма:

3+4-5*3(1+7);
f1(a,b)=a+b-3;
c=17;
4+f1(6,7)*c;

[Finch]

Читаем книгу  Ахо со товаришами. "Компиляторы. Принципы, технологии, инструменты" В электронном виде есть тут https://club.shelek.ru/viewfiles.php?id=20
Там почти вся книга посвешена этому вопросу.

[Вад]

Тебе не венгерская (польская?) нотация понадобится, а стек с термами. "Превосходство" (приоритет?) операторов определяется правилом помещения этих операторов в стек и извлечения из него. Если не принимать во внимание отдельный случай, связанный с добавлением новых термов (функций), то, опять же, понадобится структура типа "стек",  а не дерево. Возможно, я не вполне оцениваю масштабы твоего замысла, но обычные калькуляторы нас ещё на 1м или 2м курсе, кажется, учили делать именно на стеке.

[Serg79]

Вад, описанный тобой способ вычислений с помощью стековой машины, используется для вычислений математических выражений записанных именно в "обратной польской нотации". Написание данной стековой машины не составляет большого труда. Но она требует что бы на вход ей подавалось математическое выражение записанное в "обратной польской нотации".

Если мы хотим что бы стековая машина могла вычислять выражения записанные в "инфиксной нотации", то надо с начало преобразовать выражение из "инфиксной" в "обратную польскую форму" [ 5 * (3 + 2) --> 5 3 2 + * ] (вот тут и начинаются основные проблемы). Для данного преобразования можно воспользоваться алгоритмом Дейкстры, который так же основывается на использовании стека для операторов.

Так же для вычисления математических выражений записанных в инфиксной форме используют "рекурсивно нисходящие синтаксические анализаторы". ИМХО, данные синтаксические анализаторы наиболее просты в понимании и кодировании человеком.

Ну и еще есть "таблично управляемые синтаксические анализаторы". Генерируют "табличные анализаторы" с помощью специальных программ, например "YACC" или "GNU/Bison". Большинство компиляторов используют именно такие анализаторы для разбора исходных текстов.

[Вад]

Serg79, верно, но перевод к той или иной нотации можно рассматривать как часть задачи по помещению в стек. Поэтому собственно польской записи - в смысле переупорядоченной строки - тут не будет, только её эквивалент в стеке. Будет некий автомат (рекурсивный или какой ещё), работающий с текстом и помещающий элементы в стек. Деревом тогда будет только дерево рекурсии
Кстати, надо ещё подумать и повспоминать - нельзя ли производить редукцию выражений прямо так, без стека, рекурсивно.

[Джон]

Чёт вы всё в кучу собрали. Собственно говоря ОПН это просто запись, разборка исходного выражения (НЕ в ОПН) производится в стеки (два стека):

1. стек данных - они просто туда ложаться или сразу вычисляются (зависит от п.2)
2. стек операторов - приоритет текущего оператора сравнивается с вершиной стека < > =

Если выражение разобрано, то выполняется содержимое стеков (чистая ОПН). На вершине стека данных результат.

Я так даже ф-ции закручивал (приоритет равняется приоритету круглых скобок). Тоже работает.

[Serg79]

Собственно говоря ОПН это просто запись, разборка исходного выражения (НЕ в ОПН) производится в стеки (два стека):

Ну так нельзя говорить. Вычисления производятся над выражением уже преобразованным в ОПН, только применение операторов идет на лету.

[Джон]

Как это? Сначала разбираем выражение в стеки. Выполнение оператора осуществляется, если я не вру, по условию приоритет оператора в стеке больше чем приоритет текущего оператора. Когда они равны то меняются местами, а если меньше, то текущий просто ложится в стек. Те вычисления над двумя операндами из стека данных осуществляется только при одном из трёх условий.
По окончании разбора в стеки имеем именно ОПН (я не знаю используется ли такая аббревиатура, сорри, я её знаю под UPN).

Я просто хотел сказать, что вы с Вадом говорите в принципе об одном и том же. Просто со стеками это практическая реализация калькулятора с применением UPN, которая гораздо быстрее метода рекурсивного спуска. Если не ошибаюсь это "родная" реализация в языке Forth.

[Mayor]

итак предложено 4 варианта:

почитать ахо, ульмана - я не собираюсь профессионально заниматься компиляторами и данная задачка имхо имеет меньшее время реализации, чем изучение данной книги

таблично управляемый синтаксический анализатор - для меня представляет неопределенные трудности и я боюсь браться за это решение с моими знаниями

стековая машина опн - несмотря на скорость, предполагает дополнительные сложности с добавлением и пониманием алгоритма дейкстры, добавлением типа данных стек

рекурсивно нисходящий синтаксический анализатор - вроде то что нужно, несмотря на тормазнутость, имхо самое простое в реализации решение из предложенных - если я его правильно понял

[Антон (LogRus)]

Как всё это грустно.
http://algolist.manual.ru/syntax/parsear.php
http://algolist.manual.ru/syntax/revpn.php

[Mayor]

описание работы алгоритма для рнса:

3+4-5*3/(1+7);

термы верхнего порядка это +- и терм 2го порядка
1 на входе мы рекурсивно вычисляем терм2, если дальше не +-, то ошибка
2 дальше вычисляем правый терм2 и затем выполняем операцию +-, запоминая результат
3 если встечаем вместо конца строки еще один терм +-, подставляем результат вместо правого терма и возвращаемся на 2
4 возврящаем запомненый результат когда достигнут конец строки

термы 2го порядка это *\ и число, вычисляются аналогично первому порядку

какие сложности могут возникнуть при добавлении термов () и куда их лучше добавлять?

почему стековая машина опн считается более быстрой по сравнению с рнса для языков типа с\с++ с дешевым вызовом рекурсивных функций?

[Serg79]

Mayor, откуда у Тебя данные что какой то метод быстрее а какой то медленней, Ты проводил тестовые замеры?

Простота понимания метода РНСА заключается в том, что он оперирует теми же правилами при разборе выражения что и человек. Что например нельзя сказать о других методах.

[Mayor]

Mayor, откуда у Тебя данные что какой то метод быстрее а какой то медленней, Ты проводил тестовые замеры?

Просто со стеками это практическая реализация калькулятора с применением UPN, которая гораздо быстрее метода рекурсивного спуска. Если не ошибаюсь это "родная" реализация в языке Forth.

я думал, что джон проводил тестовые замеры или имеет ссылки на них

относительно скобок ()

терм 3го порядка () или число, при взятии 3го терма, если первым символом идет (, то вызывается взятие терма 1 - возникают дополнительные условия на взятие термов 1 и 2:
1 нужна какая то переменная указывающая следует ли вначале брать терм низшего порядка или он уже взят или стоит по дефолту отсылать левым термом 0 для сложения и 1 для умножения ?
2 при появлении любого чужеродного символа, например ) или завершения строки, он возвращается в буфер и функция возвращает полученный результат

[Serg79]

Mayor, после переноса темы в раздел для "начинающих" я могу Тебя спросить. Ты какие цели преследуешь своими вопросами?

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

Ты хочешь что бы Тебе написали примеры реализаций разбора простых синтаксических выражений? Тогда задавай свой вопрос в разделе "срочно пАмАгите".

Или Ты хочешь что бы на Твои типовые вопросы:

1 нужна какая то переменная указывающая следует ли вначале брать терм низшего порядка или он уже взят или стоит по дефолту отсылать левым термом 0 для сложения и 1 для умножения?

давали расширенные ответы? Ну тогда немного раскинь своими мозгами, перед постановкой вопроса.

[Mayor]

Mayor, после переноса темы в раздел для "начинающих" я могу Тебя спросить. Ты какие цели преследуешь своими вопросами?

получить на них ответы

1 насколько необходимо приведение к польской\венгерской нотации?
2 как в общем может выглядеть алгоритм, который определяет превосходство операторов?
3 скорее всего тут потребуется структура типа дерево?
4 как можно обойти явноя задания деревьев для упрощения кода?

как можно описать конкретный пример работы алгоритма:

3+4-5*3(1+7);
5) f1(a,b)=a+b-3;
c=17;
6) 4+f1(6,7)*c;

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

остался разбор частей 5 и 6 выражения, перед приступлением к написанию кода

Serg79, если ты уверен как Джон,   что имеется куча их разборов с реализацией может скинешь тройку ссылок на них

[Антон (LogRus)]

[Mayor]

да  ты дал полезные ссылки, просто у серга теоретическая подготовка в этом плане оказалась шире и он посоветовал имхо самый простейший вариант

по твоим ссылкам:
Алгоритм Рутисхаузера - нужно расставить скобки
Алгоритм Бауэра и Замельзона - ни слова о добавлении новых термов
ОПН со стековой машиной - мне просто изначально хотелось попробовать что либо инное - впрочем я сейчас увяз с добавлением термов определения и использования функций и не знаю куда их будет вставить быстрее в опнсм или рнса

[Serg79]

Mayor, Тебе для чего нужен "синтаксический анализатор"? Если для встраивания в рабочий проект, то используй программы генерации "синтаксических анализаторов" по заданной грамматике.

Использование данных программ позволяет создавать анализаторы любой сложности, они генерят качественный код и, что не мало важно данные программы проверены временем. В UNIX средах для генерации анализаторов используют YACC или GNU Bison. Они делают одно и то же, просто Bison это GNU реализация того же YACC. В Инете по Bison-у есть хорошая документация на русском.

Вот пример, ставший наверно уже классическим, простого анализатора. Он вычисляет выражения типа [ ( -3 +46 ) * 3 ] и т.п., любой сложности:

Код:

%{
#include <stdio.h>
#include <ctype.h>

#define YYSTYPE double

static void yyerror(const char *s);
static int yylex(void);
%}

%token NUMBER
%left '+' '-'
%left '*' '/'
%left NEG

%%
list:
     | list '\n'
     | list expr '\n' { printf("\t%.8g\n", $2); }

expr: NUMBER             { $$ = $1; }
    | expr '+' expr      { $$ = $1 + $3; }
    | expr '-' expr      { $$ = $1 - $3; }
    | expr '*' expr      { $$ = $1 * $3; }
    | expr '/' expr      { $$ = $1 / $3; }
    | '-' expr %prec NEG { $$ = -$2; }
    | '(' expr ')'       { $$ = $2; }
;
%%

void yyerror(const char *s)
{
    fprintf(stderr, "%s\n", s);
}

int yylex(void)
{
    int c;

    while ((c = getchar()) == ' ' || c == '\t');

    if (c == EOF)
        return 0;
        return 0;
    if (c == '.' || isdigit(c)) {
        ungetc(c, stdin);
        scanf("%lf", &yylval);
        return NUMBER;
    }

    return c;
}

int main(void)
{
    return yyparse();
}

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

Все задаваемые выше Тобой вопросы, говорят только об одном, Ты не читаешь описания алгоритмов.

[Mayor]

Mayor, Тебе для чего нужен "синтаксический анализатор"? Если для встраивания в рабочий проект, то используй программы генерации "синтаксических анализаторов" по заданной грамматике.

в рабочий проект буду встраивать питон, СА интересует только в плане тренировки

Использование данных программ позволяет создавать анализаторы любой сложности, они генерят качественный код и, что не мало важно данные программы проверены временем. В UNIX средах для генерации анализаторов используют YACC или GNU Bison. Они делают одно и то же, просто Bison это GNU реализация того же YACC. В Инете по Bison-у есть хорошая документация на русском.

этот вариант отпадает, как слишком сложный, мне нужен стянуть откуда нить описание, в крайнем случае понятную реализацию простого алгоритма  - РНСА был просто самым лучшим вариантом из предложенных

Вот пример, ставший наверно уже классическим, простого анализатора. Он вычисляет выражения типа [ ( -3 +46 ) * 3 ] и т.п., любой сложности:

пример не компилится,  ( -3 +46 ) * 3  :- разбор подобных выражений я уже нашел в ссылке на РНСА

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

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

Все задаваемые выше Тобой вопросы, говорят только об одном, Ты не читаешь описания алгоритмов.

у меня просто нет времени на 400-800 страниц из ахо ульмана, что нашел на 3-15 стр, рабирает толкьо простые математические выражения, переменные удалось вставить в алгоритм своим умом, как вставлять фукнции без понятия

[Serg79]

пример не компилится,  ( -3 +46 ) * 3  :- разбор подобных выражений я уже нашел в ссылке на РНСА

Ты как компилировать то пытался?

Говоришь что реализовал разбор вышеприведенных выражений? Слабо верится в это?

Если хочешь опровергнуть данную мысль, покажи пример рабочего кода.

[Mayor]

Ты как компилировать то пытался?

Говоришь что реализовал разбор вышеприведенных выражений? Слабо верится в это?

Если хочешь опровергнуть данную мысль, покажи пример рабочего кода.

компилил как обычно g++ имя_твоего_исходника

я спроектировал алгоритм работы программы с использованием примера из рнса и добавлением отсебятины для определения и замены переменных, непреодалимых сложностей в его реализации не вижу

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

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

[Вад]

Код: (Text)

я бы хотел добавить в проект определение и подстановку фукнций, но не знаю как

Эта задача разбивается на 2:
1. собственно разбор объявления новой функции
2. построение вычисляемой функции из "кирпичиков" на основе результатов разбора
Где именно проблема: в разборе функций или в построении составных вычислений?

В рабочую версию проекта можно добавить код чего угодно безо всякого перепроектирования, если возможность добавления чего угодно именно в это место кода уже спроектирована и заложена Плагины же в 100% приложений без перепроектирования добавляют.

[Mayor]

Код: (Text)

я бы хотел добавить в проект определение и подстановку фукнций, но не знаю как

Эта задача разбивается на 2:
1. собственно разбор объявления новой функции
2. построение вычисляемой функции из "кирпичиков" на основе результатов разбора
Где именно проблема: в разборе функций или в построении составных вычислений?

с разбором объявления проблемм не вижу
для начала интересует в какой терм ее засунуть и как отличить объявление от вызова

В рабочую версию проекта можно добавить код чего угодно безо всякого перепроектирования, если возможность добавления чего угодно именно в это место кода уже спроектирована и заложена Плагины же в 100% приложений без перепроектирования добавляют.

попробуй в версию калькулятора, написанную по принципу: производим с текущим числом считаную бинарную операцию взяв число идущее после него, прекрасно кстати работающую на:
3*4-6
добавить разбор выражения:
3*4-6\2
я думаю придется выкинуть в топку алгоритм и переписать все с 0, разве что оставив функцию ansi to int, да и ту имхо придется переписывать если потребуется разобрать выражение типа:
3.2*4.5

[Вад]

Объявление от вызова отличать элементарно. Просто у тебя есть расширяемая грамматика, и если в ней уже определён терм - то его повторное упоминание трактуется как вызов. Если не определён, то ты полагаешь его объявлением - но если синтаксис не соответствует объявлению, то выражение некорректно.

Если требуется переопределение - то можно ввести отличие объявления от вызова, которое сразу трактуется однозначно. Как define в Scheme, например.

Можно также трактовать все термы как переменные, и в таком случае замена соответствующего терму выражения просто должна иметь особую форму. Скажем,
+ = (add x y) mod 2

[Mayor]

Объявление от вызова отличать элементарно. Просто у тебя есть расширяемая грамматика, и если в ней уже определён терм - то его повторное упоминание трактуется как вызов. Если не определён, то ты полагаешь его объявлением - но если синтаксис не соответствует объявлению, то выражение некорректно.

Если требуется переопределение - то можно ввести отличие объявления от вызова, которое сразу трактуется однозначно. Как define в Scheme, например.

Можно также трактовать все термы как переменные, и в таком случае замена соответствующего терму выражения просто должна иметь особую форму. Скажем,
+ = (add x y) mod 2

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

a=b+a; /*
читаем терм 3го порядка,
в случаях когда он оказывается переменной, а не числом:
- читаем следующий терм, если следующий терм =
-- рекунсивно вызываем чтение терма 1го порядка, а полученный результат записываем в переменную
- иначе, запихиваем обратно терм, подставляем вместо переменной значение и возвращаем результат
*/

с функциями можно поступить также, но
func(a,b,c)= ...
уже сразу после чтения открывающей скобки, нужно знать, что это определение или вызов - тк от этого зависит обработка указанных аргументов
твой вариант имхо удобнее, тк не потребует чтения до закрывающей скобки +1 символ, с последующим возвращением их в поток чтения
те вводим терм define - $ к примеру
его лучше сделать термом 4 или 3го порядка?
с=3;
$func(a,b)a+b-2; // определение
func(3,c); // вызов

вызов функции как я понимаю лучше сделать термом 3го порядка, как переменную ?
хранить функции имеет смысл отдельно от переменных?
при нахождении вместо = ( проверяем ее наличие в символьной таблице функций
- при наличии создаем новую таблицу переменых согласно данным аргументам ?
вот тут снова наступает небольшая загвоздка:
реально ли организовать использование в вызове функций глобальных переменных? :
b=3;
$f(a)a*3+b;
b=4;
f(4);
-если да, то следует использовать их значения на этапе определения или вызова фукнции?

я вот подумал, основное отличие интерфейсов калькулятора с функциями и без них это:
таблица функций и необходимость временного добавления аргументов и их значений в таблицу символов(переменных)

поэтому, может имеет смысл вначале реализовать калькулятор только с переменными, если потом добавление функций не порушит его алгоритмы и интерфейсы?

[Mayor]

вчера писал калькулятор для почти второкура ССК, одного института\университета, стоящего где-то на 14 месте в рейтинге российских вузов:

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

попытался узнать как им пытались объяснить работу калькулятора:

что такое структуры данных - он без понятия

не знает названия ни одного алгоритма сортировки, не может назвать временной сложности любого алгоритма сортировки

вроде умеет пользоваться функциями, когда-то слышал про рекурсию, умеет немного пользоваться cout,cin и некоторыми функциями библиотек cmath,
string вроде не проходил, но быстро понял, что к чему, вроде наслышан про массивы, но не в теме динамически выделяемой памяти

я фигею за преподов, как они при таком уровне знаний студента пытаются дать ему написание калькулятора?

быстрее всего оказалось ему будет объяснить работу РНСА на конкретном примере:

Код:

/* примитивный нисходящий рекурсивный синтаксический анализатор
   * объяснение алгоритма смотри в Dragon Book
   ** Compilers: Principles, Techniques, and Tools
   ** by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman
   * пояснение реализации:  The C++ Programming Language 
   ** by Bjarne Stroustrup 
   ** Addison-Wesley Pub Co; 3rd edition (February 15, 2000); ISBN 0-201-70073
   * вход строка содержащая числа, sqr(), () и операторы + - / *  
   * выход результат
   */

#include <string>
using std::string;
#include <istream>
using std::istream;
#include <cmath>
using std::sqrt;
struct calc_err {};
struct term_err: public calc_err { // еще не определенный терм
	char c;
	int term_lvl;
	term_err(char cc,int lvl):c(cc),term_lvl(lvl) {}
};
struct par_err: public calc_err {}; // отсутсвует закрывающая скобка
struct sqrt_err: public calc_err {}; // в функцию корня передано отрицательное выражение

template<class T> T term1(istream& f) ;  
// разбирает выражения вида term3
// где term3 может быть: число, выражение в скобках (), sqrt() 
template<class T> T term3(istream& f) {  
	T t=0;
	char c=0;
	f>>c;
	if(isdigit(c)) {
		f.putback(c);
		f>>t;
		return t;
	}
	if(c=='(') {
		t=term1<T>(f);
		f>>c;
		if (c!=')') throw par_err();
		return t;
	}
	if(c=='s') {
		string s;
		f>>s;
		t=term1<T>(f);
		if(t<0) throw sqrt_err();
		t=sqrt(t);
		f>>c;
		if (c!=')') throw par_err();
		return t;
	}

	throw term_err(c,3);
}
	
// разбирает выражения term3[{*|/}term3]
template<class T> T term2(istream& f) {  
	T t=term3<T>(f);
	char c=0;
	while(f>>c) {
		switch(c){
			case '/': t/=term3<T>(f);break;
			case '*': t*=term3<T>(f);break;
			default: f.putback(c);return t;
		}
	}
	return t;
}
// разбирает выражения term2[{+|-}term2]
template<class T> T term1(istream& f) {  
	T t=term2<T>(f);
	char c=0;
	while(f>>c) {
		switch(c){
			case '+': t+=term2<T>(f);break;
			case '-': t-=term2<T>(f);break;
			default: f.putback(c);return t;
		}
	}
	return t;
}

вот тут-то и возник вопрос, к этой хрени сложно будет прикрутить переменные и формулы, или проще будет переписать все с 0 ?