#java #algorithm
#java #алгоритм
Вопрос:
Итак, это немного другой взгляд на старый java-пример rock, paper, scissors. В этой ситуации пользователь вводит входные данные (которые, как я предполагаю, являются действительными, т. Е. Использует Только комбинации R, P, amp; S и имеет соответствующие круглые скобки, также без пробелов), например, (Ramp;S) вывод происходит R потому, что Камень бьет ножницы или ((Ramp;S)amp;(Pamp;R)) выводит P .
Сейчас у меня есть код (ниже), который может разделять строки, перебирать и получать буквы, используемые в списке, потому что моя идея заключалась в том, чтобы просто читать слева направо, оценивая, пока я не дойду до конца, но на данный момент я в тупике, потому что какой был бы хороший способследите за всеми «предыдущими» результатами. Нужен ли мне еще один пустой список? Также использование cases не представляется жизнеспособным, поскольку входные данные могут быть длинными, а также полностью случайной комбинацией 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("amp;");
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") amp;amp; list.contains("S")){ //ex. if the input was "(Ramp;S)"
System.out.println("R");
break;
}
}
}
}
Комментарии:
1. Потенциальная сложность и вложенность этого велики, и мне интересно, может ли быть формальный лексер / синтаксический анализатор, такой как ANTLR4, быть тем, что вы хотите использовать.
2. Пожалуйста, рассмотрите возможность использования структуры стека для этой проблемы. Таким образом, вы можете оценивать простые операции по ходу выполнения и возвращать результат в стек для дальнейшего использования.
3. Что бы
Ramp;Rэто дало?4. @btilly ах да, это было бы R, и то же самое с S amp; S, P amp; P. Также отдельные входные данные R, P, S будут просто самими собой
Ответ №1:
Одним из способов решения этой проблемы было бы написать рекурсивную evaluate функцию. В качестве входных данных потребуется строка, базовым регистром которой является один символ R , P , или S . В противном случае он разделил бы строку на амперсанд верхнего уровня и рекурсивно оценил бы строку слева и справа от амперсанда и использовал возвращенные символы для определения результата. Амперсанд верхнего уровня может быть найден как амперсанд, встречающийся не в наборе круглых скобок (не считая самых внешних избыточных круглых скобок, если они существуют).
Например, вот реализация на 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 amp;amp; 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 amp;amp; c == 'amp;') {
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("((Ramp;S)amp;(Pamp;R))"));
System.out.println(evaluate("(Ramp;S)amp;(Pamp;R)"));
System.out.println(evaluate("(R)"));
System.out.println(evaluate("((((Ramp;P))amp;((S))))"));
System.out.println(evaluate("((Ramp;S)amp;R)"));
System.out.println(evaluate("S"));
System.out.println(evaluate("(((Ramp;P)amp;(Samp;P))amp;(Pamp;R))"));
}
}
Вывод:
P
P
R
S
R
S
S
Комментарии:
1. Для моего первоначального ответа я предположил, что входные данные не имеют избыточных круглых скобок, а также что самое внешнее выражение заключено в круглые скобки. Я обновил приведенное выше решение, чтобы ослабить эти предположения. Например,
(Ramp;S)amp;(Pamp;R)и(((Ramp;S)))не будет работать с моим оригинальным решением, но они работают сейчас.
Ответ №2:
Если вы обработаете свой ввод и преобразуете его в обратную польскую нотацию, вы можете использовать a Stack для хранения значений и операторов.
Вот что я имею в виду. Возьмите свой простой ввод.
(Ramp;S)
На a Stack это будет выглядеть так:
R
S
amp;
Стек всегда должен начинаться с двух значений и одного оператора.
Давайте рассмотрим ваш более сложный пример.
((Ramp;S)amp;(Pamp;R))
На a Stack это будет выглядеть так:
R
S
amp;
P
R
amp;
amp;
Вы бы заменили RSamp; на Stack результат. Затем вы бы заменили PRamp; на Stack результат. Конечный результат будет обработан с помощью последнего amp; оператора.
Комментарии:
1. Алгоритм для замены этого на RPN должен быть примерно таким же сложным, как и исходная задача.
2. ДА. Но преобразование «инфикса» в RPN — хорошо известная проблема с хорошо известными решениями.
3. Так же, как и синтаксический анализ инфиксных обозначений с помощью двоичного оператора. Смотрите blog.erezsh.com /… например. Если вы не объяснили алгоритм, который знаете, а OP — нет, ваше предложение не сильно поможет OP.
Ответ №3:
Один из способов решить эту проблему — сначала разобрать строку в дерево, где узлами являются либо 1) символ, либо 2) группа дочерних узлов, представляющих элементы в круглых скобках. Затем вызовите рекурсивную функцию вычисления в дереве.
Например, вот реализация на Java, которая имеет проверку ошибок и поддержку пробелов (которые игнорируются), за которой следует мой первоначальный прототип на Python, который короче, но не включает проверку ошибок и поддержку пробелов.
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('amp;'))
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('amp;');
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("((Ramp;S)amp;(Pamp;R))")); // P
System.out.println(evaluate("(Ramp;S)amp;(Pamp;R)")); // P
System.out.println(evaluate("( R )")); // R
System.out.println(evaluate("((((Ramp;P))amp;((S))))")); // S
System.out.println(evaluate("((Ramp;S)amp;R)")); // R
System.out.println(evaluate("S")); // S
System.out.println(evaluate("(((Ramp;P)amp;(Samp;P))amp;(Pamp;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('((Ramp;S)amp;(Pamp;R))')) # P
print(evaluate('(Ramp;S)amp;(Pamp;R)')) # P
print(evaluate('(R)')) # R
print(evaluate('((((Ramp;P))amp;((S))))')) # S
print(evaluate('((Ramp;S)amp;R)')) # R
print(evaluate('S')) # S
print(evaluate('(((Ramp;P)amp;(Samp;P))amp;(Pamp;R))')) # S