What are known approaches to graphing algebraic expressions?

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`.