In this assignment we would like to implement a version of the rock paper scissors game, where the character R represents rock, P represents paper, and S represents scissors. The expression (R&S) represents a game between the rock and the scissors, and therefore the winner (and the outcome) will be R. We can also have morc complicated expressions. For example, ((P&S)&(R&P)) will be cquivalent to (S&P) which in turn is equivalent to S. (You can think of the expression as a kind of rock paper scissors tournament and the result is the winner of the tournament!) Note the input may or may not be "valid". We define valid input (recursively) as follows: R, P, and S are valid (single-character) inputs. (A&B) is also valid as long as A and B are valid. Note this means that, for instance we have: R is valid (and the outcome is just R). (R&R) is valid (and we define the outcome to be R). (R&P&S) is invalid. R&P is invalid. (R&(P)) is invalid. )R&S( is invalid. ((R&S)) is invalid. (A&B) is invalid (invalid characters) (R& P) is invalid (invalid character(i.c., spacc)) 1. [50 points: 10 for public tests, 15 for private tests, 15 for source code, 10 for styling] Write a program that given an input, outputs either "VALID" or "INVALID" depending on the input. For this question you can assume The input is a single linc. The length of the input is at most 1000 characters. Input Sample Output Sample (R& (P& ((P&R)& (R&R)))) VALID Here is another example. Input Sample Output Sample R&(R&P) INVALID