Recursively verifying if a string is a valid prefix expression?

I'm rather new to the community but I've seen some helpful posts on here so I thought I'd ask.

I've got a homework question that asks us to recursively check whether a given string is a valid prefix expression given by the t开发者_运维问答wo following rules (standard):

1. Variables (a-z) are prefix expressions
2. If O is a binary operator and F and E are prefix expressions, OFE

Now, I kind of get the evaluation and have looked at the prefix-to-infix algorithms, but I can't for the life of me figure out how to implement just the evaluation methods (as I only need to check if it's valid, so not +a-b for example).

I know most of the implementation for these problems is done using stacks but I don't see how I would do it recursively here... some help would be tremendously appreciated.

Think of it this way. (I'm not going to write the code, since that's what you need to learn).

You want to check if a certain string is a prefix expression, so you have a function:

boolean isPrefix(string)

Now, there's two way that string could be a prefix:

1. It's a character from a-z
2. It's in the format O(prefix)(prefix)

So first, you check if the string has a length of one and is between a-z, and if so, the answer is yes.

Next you can check if the string starts with an O. If it does, you need to test the rest of the string to see if it is composed of two prefix expressions (FE).

So you start iterating from 1 to length, and passing each substring (0->i, i->length) into isPrefix(). If both substrings are also valid prefix expressions, the answer is yes.

Otherwise, the answer is no.

That's pretty much it, but the implementation, however, is up to you.

I'm not sure I entirely understand the point of this, but I imagine you should have some method like checkPrefixIn(String s) that looks at only part of the given String, returns true if it is only a prefix, false if it is only an operator (or invalid character), or the return value of checkPrefixIn(partOfS), where partOfS is a substring of the input s