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

Ну и не следует упускать из внимания тот фактор, что большой объем кода потенциально может нести и большое количество уязвимостей. И то, что код открыт, совершенно не означает, что даже крутой профессионал способен быстро найти потенциальные уязвимости в таком коде.

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

Спасибо за наводку на алгоритм сортировочной станции. Что касается библиотек типа указанной Вами, то меня сильно напрягают их размеры, а также зависимости от других библиотек. С этой точки зрения работу можно назвать экспериментом на тему того, можно ли писать полнофункциональные приложения на современном чистом JS без использования сторонних библиотек. Конечно же при допущении, что поддержка старых браузеров не нужна.

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

Ну про массивы все просто. В JS в отличие от, например, Java или C#, нет стека как специально выделенной структуры данных, а его интерфейс в виде функций push и pop реализован на массиве.

Кстати, в репозитории, на который Вы дали ссылку, функция evaluate также выполняется на стеке в виде массива, плюс там используются временные переменные, которых у меня нет, так как два стека передаются по ссылке в виде аргументов функции вычисления промежуточных результатов, в которой и обрабатываются. Хотя довольно интересно сравнить эту и мою реализацию на больших объемах вычислений.

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

Ок. Если Вам так будет удобнее, можно назвать представленный алгоритм как стековую машину, производящую вычисления по обратной польской записи, как это сформулировано на ru.wikipedia.org/wiki/Обратная_польская_запись

За ссылку спасибо. А вот на тему обратной польской нотации просто задайте себе вопрос — а для чего она вообще нужна, если не для обслуживания определенных структур данных. Повторюсь, но в свое время выпускались стековые калькуляторы, такие как ru.wikipedia.org/wiki/Электроника_МК-61, у которых в инструкциях для пользователей примеры вычислений приводились именно в обратной польской нотации, которая сама по себе, вне контекста стекового калькулятора, выглядела жутко неудобной и непонятной. Но вот после обуздания стекового калькулятора, на котором можно было еще и программировать, привычные всем бытовые калькуляторы выглядели палкой-копалкой на фоне экскаватора.

Ошибаетесь. Обратная польская нотация — это именно про стеки. В свое время даже выпускались стековые калькуляторы, такие как ru.wikipedia.org/wiki/Электроника_МК-61, где в инструкциях примеры ввода и последующего расчета проводились именно в обратной польской нотации.

То есть выражение 1+2-3 будет передано на вычисление в виде двух стеков:
массив операндов: [1, 2, 3]
массив операторов: ["+", "-"]
Чем не обратная польская запись?

1. Запись (1+1) превращается в два стека (в виде массивов) перед передачей ее расчетной функции calcExpression после обнаружения закрывающей скобки:
массив операндов: [1, 1]
массив операторов: ["(", "+"]
2. Функция calcExpression после вычисления возвращает следующие стеки:
массив операндов: [2]
массив операторов: ["("]
3. Функция calc после возврата значения функцией calcExpression выбрасывает из стека открывающую скобку, в результате чего стеки имеют следующий вид:
массив операндов: [2]
массив операторов: []
4. В завершении цикла обхода токенов функция calc снимает из стека операндов последний результат, то есть 2

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

Смысл публикации довольно прост — поделиться с сообществом своими мыслями и получить на них обратную связь. Про обратную польскую нотацию, честно говоря, не совсем понял. Вы уже второй, который не видит ее в алгоритме. Вот здесь довольно много примеров реализации обратной польской нотации на стеках: https://ru.wikiversity.org/wiki/Обратная_польская_запись:_примеры реализации.

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

Алгоритм, который Вы предлагаете, вполне имеет право на существование. Просто я реализовал на JS свой алгоритм 20-летней давности на Java, когда еще в Java еще не было нормальной поддержки регулярных выражений, а приходилось работать с отдельными символами строки. Тем не менее, этот алгоритм вроде бы достаточно быстр, но хотелось бы получить объективную сравнительную оценку со стороны, ради которой и сделал эту публикацию.

Добавил уточнение про деление на 0 в статью.

Прошу прощения, что забыл упомянуть про специфику расчетчика. Обработка выражения 1/0 эквивалентно созданию функции if ( B != 0; A/B; 0). Данную функцию приходится постоянно писать в Excel при выполнении различных отчетов, иначе таблица превращается в нагромождение сообщений об ошибках. А в специализированном экономическом программном обеспечении, используемом в нашей организации, данное умолчание используется более 10 лет, поэтому как-то и подзабыл.

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

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

Честно говоря, только сейчас об этом узнал. В результате в Википедии нашел следующую фразу: «Иногда в компьютерных системах и языках программирования значок возведения в степень имеет левую ассоциативность, в отличие от принятого в математике соглашения о правой ассоциативности возведения в степень».

С другой стороны, расчетчик предназначен для электронных таблиц и разбора Excel-подобных формул, где используется классический математический подход. Кроме того, скобки никогда лишними не бывают (в разумных количествах) — они если и не меняют последовательность расчетов, то могут повысить читаемость формул.

Видимо мы все же говорим о разных прикладных аспектах. В моем случае для вычисления значений по двум аргументам, значения которых содержатся в ячейках A1 и A2, в любой другой ячейке электронной таблицы нужно написать следующую формулу, в которую можно еще добавить округление до 2 знаков после запятой:

=round2((A1^2+A2^2)^0.5)

Проверить работу формулы при изменении исходных значений можно на bizcalc.ru (формулу нужно будет прописать вручную).

Так как используется единственный оператор возведения в степень, то без скобок вычисления производятся слево направо. То есть верен первый вариант 4^3^2= (4^3)^2= 4096. Сработает также вариант со скобками 4^(3^2)= 262144. Можете потестировать на bizcalc.ru.

Можете привести ссылки на реализацию вычислений, а не форматирования строк?

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

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