java - 石头、纸、剪刀游戏的算法

Question

所以这是对古老的石头、纸、剪刀 java 例子的一个稍微不同的看法。在这种情况下，用户输入输入（我假设是有效的，即仅使用 R、P 和 S 的组合，并且有匹配的括号，也没有空格），例如，(R&S)输出是R因为 Rock beats Scissors ，或((R&S)&(P&R))输出P。

现在到目前为止，我有代码（如下）可以拆分字符串，遍历并将使用的字母放入列表中，因为我的想法只是从左到右阅读，评估直到我读到最后，但此时我我很难过，因为什么是跟踪所有“先前”结果的好方法。我需要另一个空列表吗？使用案例似乎也不可行，因为输入可能很长，而且 R、P 和 S 的完全随机组合。任何建议都值得赞赏！

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;
            }
        }

    }

}

标签： javaalgorithm

Answer 1

解决此问题的一种方法是首先将字符串解析为树，其中节点是 1) 一个字符或 2) 一组表示括号中项目的子节点。然后在树上调用递归评估函数。

例如，这是一个 Java 实现，它具有错误检查和对空格（被忽略）的支持，然后是我在 Python 中的初始原型，它更短，但不包括错误检查也不支持空格。

爪哇

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