0

I need to implement an expression evaluator with some custom types, it is easy to evaluate expressions with only numbers or variables with the help of postfix (or prefix) notation but how to extend the postfix (or prefix) form to support functions with arbitrary parameters?

Infix postfix
(3+2)*2 32+2*
funone(funtwo(3), 2) * 2 ??????

How to convert the expression with function calls to postfix and evaluate it there are any standard algorithms for it?

I have looked at expr-eval-web and expr-eval-github the library saying it is modified version of Raphael Graf’s ActionScript Expression Parser and provided a link for it but i think it is not valid anymore. where can i find algorithm for Raphael Graf’s ActionScript Expression Parser ?

srilakshmikanthanp
  • 2,231
  • 1
  • 8
  • 25
  • I think it would help others help you if you say something about the context in which you're trying solve this problem -- maybe edit your question to say something about the bigger picture. – Robert Dodier Apr 17 '23 at 18:57
  • You can find plenty of both Forth (postfix) and Scheme (prefix) interpreters in JavaScript. If you want infix to one of those, read https://en.wikipedia.org/wiki/Shunting_yard_algorithm. – btilly Apr 17 '23 at 19:13
  • Does [this answer](https://stackoverflow.com/a/47761792/5459839) present what you need? – trincot Apr 18 '23 at 06:50

1 Answers1

0

It is not clear from your question if (1) you have a postfix (or prefix) notation interpreter that you use now to evaluate code like 3 2 + 2 * (and presumably (* (+ 3 2) 2)) and you need information on how the function call would look like in postfix (or prefix) notation to then update your interpreter to support function calls, or (2) you are asking how to actually programmatically parse code in some language for which funone(funtwo(3), 2) * 2 is valid (many languages can look like this).

If (1) then here are the examples:

For this: funone(funtwo(3), 2) * 2

The postfix notation would be: 3 funtwo 2 2 funone 2 *

The prefix notation would be: (* (funone (funtwo 3) 2) 2)

If (2) then there is no general ready algorithm that will look for your language out of the box (unless this is a well-known language, but you didn't say it in your question).

Generally if you need to write a parser then either:

  • you can find something ready if that is a well-known language
  • you have to write a lexer and parser yourself
  • you have to write a grammar for a parser generator

Here is a comparison of parser generators. They vary so widely that it is really impossible to recommend anything specific knowing so little about your requirements, but maybe reading about them can get you started:

rsp
  • 107,747
  • 29
  • 201
  • 177
  • I need an algorithm to parse and evaluate an expression with function calls not specifically postfix or prefix? Is thare any? Thanks. – srilakshmikanthanp Apr 17 '23 at 17:42
  • As I wrote in my answer, there is no algorithm to parse and evaluate any language. Every language has its own compiler or interpreter (or often many compilers). You need to create a lexer, parser and interpreter for your language (manually or generated) which include many algorithms by its own, and not trivial ones at that, or choose a language that has an existing set of those that can be embedded easily in your runtime (which you even didn't say what it is). Search for "embedded languages", e.g. here is a list of some those: https://github.com/dbohdan/embedded-scripting-languages – rsp Apr 17 '23 at 18:09
  • If you need pure algorithms instead of existing tools, as you seem to be saying, then I highly recommend [the courses by Dmitry Soshnikov](http://dmitrysoshnikov.com/) like "Building a Parser" and "Parsing Algorithms". Some of his examples are using a simple language with prefix notation, other a more complex language with C-like syntax. – rsp Apr 17 '23 at 18:13