I am planning to build an expression parser that will be used to graph algebraic

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.