#Recursively call for the expression minus the final term. Return $last_num unless defined $last_op My $last_num = pop $last_op = pop case: return the number if there is just a number That helps keep the parentheses from all building up on one side. Because + and * are distributive, it randomizes the order of the terms for those operators. Update: here is an algorithm in Perl to generate the display form. Rather than trying to generate the displayed form directly, just come up with a list of operators in random order, and derive the display form of the expression from that.ĭeriving the display form is a relatively simple recursive algorithm. The parentheses in the "hard" expression represent order of evaluation. I therefore suggest that you assign a rather high probability p to the rule E -> I such that you end up with a fairly small expression with high probability.ĮDIT: If you're worried that the above grammar produces too many parenthesis, look at Sebastian Negraszus' answer, whose grammar avoids this problem very elegantly. Where l(n) denotes the expected length of the arithmetic expression after n applications of production rules. The expected length of an expression is subject to the recurrence relation l(0) = 1 Therefore, the expected number of integers in a formula produced by the above algorithm is actually infinite. Note that for the above grammar and algorithm, the probability of expanding an expression E into a terminal symbol I is only p = 1/3, while the probability to expand an expression into two further expressions is 1-p = 2/3. All Expression subclasses are required to implement an evaluate method, which works recursively on the tree structure defined by these objects and effectively implements the composite pattern. The latter two then would have a leftExpression and rightExpression. I assume you would choose to represent an expression with an interface Expression which is implemented by classes IntExpression, AddExpression and MultiplyExpression. Here's an example of the application of this algorithms: E Replace all terminal symbols I by random integers.Repeat steps 2 - 4 until only terminal symbols are left.Choose uniformly at random one of the production rules for that symbol, and apply it.Choose uniformly at random one of the non-terminal symbols.Start with E as the single symbol of the output word.Based on this definition, we can randomly build a valid arithmetic as follows: The above definition for E has three production rules. Here, E is an expression (i.e., a word of your language) and I is a terminal symbol (i.e., it's not expanded any further) representing an integer. Here's a formal description of a simplified algebraic grammar supporting only addition and multiplication: E -> I You are looking to randomly generate words (algebraic expression) from a given language (the infinite set of all syntactically correct algebraic expressions). Here's a theoretic interpretation of your problem. If my question needs any clarification, please ask in the comments. If your answer gives a solution handling this one, that's great. Those examples did not include the : operator, as I only want to manipulate ints, and this operator adds many verifications. I'm not looking for anything language-related, but for the record, I'm thinking of implementing it in Objective-C, as that's the language I'm most working with recently. If you take that in consideration in your answer, that's great. This can be done either after the expression is generated, or during its creation. with the beginning of the algorithm, or a general structure of it.Īlso note that I will have to evaluate those expressions. If you see a good way to start, I'd appreciate a lead in the right direction, e.g. I'd like to know which way you believe is the best to go, between the solutions I considered, and your own ideas.
0 Comments
Leave a Reply. |