Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
Shunting Yard is for parsing. Why would you run it more than once for a given function definition? –  delnan 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. –  jeremynealbrown 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? –  delnan Mar 31 '12 at 19:21

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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