Algorithm for rock, paper, scissors game

So this is a slightly different take on the age old rock, paper, scissors java example. In this situation, the user enters the input (that I'm assuming is valid, i.e. uses only combinations of R,P, & S, and has matching parenthesis, also no spaces) like for example, (R&S) the output is R because Rock beats Scissors, or ((R&S)&(P&R)) outputs P.

Now so far I have code (below) that can split the strings, iterate through and get the letters used into a list, because my idea was just to read from left to right, evaluating until I get to the end but at this point I'm stumped because what would be a good way to keep track of all the "previous" results. Would I need another empty list? Also using cases doesn't seem viable since the input can be long and also completely random combination of R,P, and S. Any advice is appreciated!

import java.util.ArrayList;
import java.util.Scanner;

public class RPS {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        str = str.replaceAll("\\(", "").replaceAll("\\)","");
        String inputs[] = str.split("&");
        ArrayList<Object> list = new ArrayList<>();

        for (int i = 0; i < inputs.length; i++){
            if (inputs[i].substring(0, 1).contains("R")) {
                list.add(inputs[i]);
            } else if (inputs[i].substring(0, 1).contains("S")) {
                list.add(inputs[i]);
            } else if (inputs[i].substring(0, 1).contains("P")) {
                list.add(inputs[i]);
            }
        }
        for (int i = 0; i < list.size(); i++){
            if (list.contains("R") && list.contains("S")){ //ex. if the input was "(R&S)"
                System.out.println("R");
                break;
            }
        }

    }

}

If you process your input and convert it to reverse polish notation, you can use a Stack to hold the values and the operators.

Here's what I mean. Take your simple input.

(R&S)

On a Stack, it would look like:

R
S
&

The stack should always start with two values and one operator.

Let's take your more complicated example.

((R&S)&(P&R))

On a Stack, it would look like:

 R
 S
 &
 P
 R
 &
 &

You'd replace the RS& on the Stack with the result. Then you'd replace the PR& on the Stack with the result. The final result would be processed with the last & operator.

One way to solve this would be to write a recursive evaluate function. It would take a string as input, with the base case being a single character R, P, or S. Otherwise, it would split the string on the top-level ampersand, and recursively evaluate the string to the left and right of the ampersand, and use the returned characters to determine the result. The top-level ampersand could be found as the ampersand occurring not within a set of parentheses (not counting any outermost redundant parentheses if they exist).

For example, here's an implementation in Java.

import java.util.Stack;

public class RPS {
    // Normalize string by removing surrounding parentheses that are redundant.
    private static String normalize(String s) {
        // First, count the number of leading open parentheses.
        int leading = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) != '(')
                break;
            ++leading;
        }
        if (leading > 0) {
            // For each closing parenthesis, compute the position of the
            // matching opening parenthesis. The set of trailing parentheses
            // paired with leading parentheses are redundant.
            Stack<Integer> stack = new Stack<Integer>();
            for (int i = 0; i < s.length(); ++i) {
                char c = s.charAt(i);
                if (c == '(') {
                    stack.push(i);
                } else if (c == ')') {
                    int j = stack.pop();
                    if (j < leading && j + i + 1 == s.length())
                        return s.substring(j + 1, s.length() - j - 1);
                }
            }   
        }
        return s;
    }
    
    private static char evaluate(String s) {
        s = normalize(s);
        // A single character evaluates to itself
        if (s.length() == 1)
            return s.charAt(0);
        // Find the position of the top-level ampersand, which is the ampersand
        // occurring outside matched pairs of parentheses.
        int depth = 0;
        int position = -1;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(')
                depth += 1;
            else if (c == ')')
                depth -= 1;
            else if (depth == 0 && c == '&') {
                position = i;
                break;
            }
        }
        // Otherwise, split on the top-level ampersand and evaluate the left
        // and right sides.
        char left = evaluate(s.substring(0, position));
        char right = evaluate(s.substring(position + 1));
        // Return the winner
        if (left == right)
            return left;
        switch (left) {
            case 'R':
                return right == 'P' ? 'P' : 'R';
            case 'P':
                return right == 'S' ? 'S' : 'P';
            case 'S':
                return right == 'R' ? 'R' : 'S';
            default:
                throw new RuntimeException();    
        }
    }
    
    public static void main(String[] args) {
        System.out.println(evaluate("((R&S)&(P&R))"));
        System.out.println(evaluate("(R&S)&(P&R)"));
        System.out.println(evaluate("(R)"));
        System.out.println(evaluate("((((R&P))&((S))))"));
        System.out.println(evaluate("((R&S)&R)"));
        System.out.println(evaluate("S"));
        System.out.println(evaluate("(((R&P)&(S&P))&(P&R))"));
    }
}

Output:

P
P
R
S
R
S
S

One way to solve this is to first parse the string into a tree where nodes are either 1) a character or 2) a group of children nodes representing items in parentheses. Then call a recursive evaluation function on the tree.

For example, here's an implementation in Java that has error checking and support for white spaces (which are ignored), followed by my initial prototype in Python, which is shorter, but does not include error checking nor support for white spaces.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class RPS {
    private static class Node {
        Character data = null;
        List<Node> children = null;
    }
    
    private static Node parse(Queue<Character> tokens) {
        // WARN: Destructively modifies input
        char token = tokens.remove();
        Node node = new Node();
        if (token == '(') {
            node.children = new ArrayList<Node>();
            while (tokens.peek() != ')') {
                node.children.add(parse(tokens));
            }
            char c = tokens.remove();
            if (c != ')')
                throw new RuntimeException();
        } else if (token == ')') {
            throw new RuntimeException();
        } else {
            node.data = token;
        }
        return node;
    }
    
    private static char _evaluate(Node tree) {
        if (tree.data != null) {
            return tree.data;
        } else if (tree.children.size() == 1) {
            return _evaluate(tree.children.get(0));
        } else {
            char left = _evaluate(tree.children.get(0));
            if (!tree.children.get(1).data.equals('&'))
                throw new RuntimeException();
            char right = _evaluate(tree.children.get(2));
            // Return the winner
            if (left == right)
                return left;
            switch (left) {
                case 'R':
                    return right == 'P' ? 'P' : 'R';
                case 'P':
                    return right == 'S' ? 'S' : 'P';
                case 'S':
                    return right == 'R' ? 'R' : 'S';
                default:
                    throw new RuntimeException();    
            }
        }
    }
    
    private static Set<Character> VALID_CHARS =
            new HashSet<Character>() {{
                add('(');
                add(')');
                add('&');
                add('R');
                add('P');
                add('S');
            }};
    
    public static char evaluate(String s) {
        Queue<Character> tokens = new LinkedList<Character>();
        tokens.add('(');
        for (int i = 0; i < s.length(); ++i) {
            char c = Character.toUpperCase(s.charAt(i));
            if (Character.isWhitespace(c))
                continue;
            if (!VALID_CHARS.contains(c))
                throw new RuntimeException();
            tokens.add(c);
        }
        tokens.add(')');
        Node tree = parse(tokens);
        char c = _evaluate(tree);
        return c;
    }
    
    public static void main(String[] args) {
        System.out.println(evaluate("((R&S)&(P&R))"));          // P
        System.out.println(evaluate("(R&S)&(P&R)"));            // P
        System.out.println(evaluate("( R )"));                  // R
        System.out.println(evaluate("((((R&P))&((S))))"));      // S
        System.out.println(evaluate("((R&S)&R)"));              // R
        System.out.println(evaluate("S"));                      // S
        System.out.println(evaluate("(((R&P)&(S&P))&(P&R))"));  // S
    }
}

Python

from collections import deque
from typing import Union

def parse(tokens: deque):
    # WARN: Destructively modifies input
    token = tokens.popleft()
    if token == '(':
        result = []
        while tokens[0] != ')':
            result.append(parse(tokens))
        tokens.popleft()  # closing ')'
        return result
    else:
        return token

def _evaluate(tree: Union[list, str]):
    if type(tree) != list:
        return tree
    elif len(tree) == 1:
        return _evaluate(tree[0])
    else:
        left = _evaluate(tree[0])
        right = _evaluate(tree[2])
        pair = left + right
        lookup = {
            'RP': 'P', 'PR': 'P', 'PP': 'P',
            'RS': 'R', 'SR': 'R', 'RR': 'R',
            'PS': 'S', 'SP': 'S', 'SS': 'S',
        }
        return lookup[pair]

def evaluate(s: str):
    tokens = deque(f'({s})')
    tree = parse(tokens)
    return _evaluate(tree)

# Example usage
print(evaluate('((R&S)&(P&R))'))          # P
print(evaluate('(R&S)&(P&R)'))            # P
print(evaluate('(R)'))                    # R
print(evaluate('((((R&P))&((S))))'))      # S
print(evaluate('((R&S)&R)'))              # R
print(evaluate('S'))                      # S
print(evaluate('(((R&P)&(S&P))&(P&R))'))  # S