I am planning to build an expression parser that will be used to graph algebraic functions ( think TI-83 ) with JavaScript.

Functions will take the form of f(x)=

Aside from typical operators such as: + - * / ^

I'd also like to add support for inline functions such as: sin(), cos(), log() and random().

I have looked at implementing the Shunting Yard algorithm for parsing expressions, but it does not look like an efficient approach to evaluating a function with a hundreds or thousands of inputs. What other known algorithms exist for this task?

  • Shunting Yard is for parsing. Why would you run it more than once for a given function definition? – user7043 Mar 31 '12 at 18:06
  • I might be thinking about this wrong, but it seems that I would need to run the algorithm for each value of x. – JeremyFromEarth Mar 31 '12 at 18:46
  • Is it possible that you evaluate the function directly while running shunting yard, instead of building a simpler representation (such as Reverse Polish Notation - RPN for short) of the function, as it's intended? – user7043 Mar 31 '12 at 19:21
  • The Wikipedia article has a link to another algorithm: Operator-precedence parser – rwong Jul 17 '15 at 22:08

Shunting Yard is O(n) on the length of the function. You can't get any better asymptotic complexity than that, so you're left with potential linear speedup. The only thing I can think of that might be faster is to translate the function into native javascript and use eval. You definitely want to benchmark that, though. Another thing to do would be to only generate the RPN version once, then just execute that for each value of x.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.