В поисках сбалансированной скобки, включающей математику
Я пытался решить этот вопрос в течение последних нескольких часов, и я просто не понимаю его. Я знаю, что для этого нужно какое-то математическое вычисление, но я не знаю, как точно его вычислить. Я знаю, что этот код не имеет смысла, потому что я полностью потерян, я был бы признателен за любые подсказки или помощь для этого, чтобы помочь мне приблизиться к решению.
Я спросил своего профессора, и он намекнул, что это похоже на перестановку / комбинацию с использованием алфавита, например 26^3, для 3 различных комбинаций, но это мне не сильно помогло.
Что я знаю:
Есть 796 символов для ввода данных в строке, и я должен найти ВСЕ возможные способы, которыми 796 символов могут быть в форме сбалансированных скобок.
Поскольку он должен начинаться с '(' и заканчиваться на ')', для каждого случая должно быть 2 скобки. Так что это может быть '()()(xc)(cvs)'. Таким образом, это означает, что математический расчет должен включать 2*(что-то) на символ (ы), так как он должен быть сбалансирован.
Мне нужно использовать оператор остаток (%), чтобы рекурсивно найти каждый случай, но как мне это сделать, когда я беру
char
в неint
?
Что я не знаю:
Как я буду анализировать каждый случай? Не займет ли это много времени или много кода без простой формулы для расчета ввода?
Мне нужно много
if
Заявления или рекурсия?
Вопрос:
Пусть Σ = {), (}. Пусть L ⊆ Σ* - множество строк правильно сбалансированных скобок. Например, (())() находится в L и (())) (не в L. Формально L определяется рекурсивно следующим образом.
ε ∈ L
Строка x ≠ ε находится в L тогда и только тогда, когда x имеет вид (y)z, где y и z находятся в L.
n - это конкретное трехзначное число от 0 до 999.
Вычислить F (N) мод 997
Некоторые факты, которые могут оказаться полезными: если n1, n2 является членом N(натуральное число), то
(n1 x n2) мод 997 и (n1 + n2) мод 997
n = 796 (это специфично для меня, и в данном случае это будет входная информация)
Поэтому я должен "вычислить f(796) mod 997 =?" используя программу. В этом случае я просто буду использовать Java для этого вопроса.
Код:
import java.util.*;
public class findBrackets
{
public static void main(String[] args)
{
String n;
int answer = 0;
Scanner input = new Scanner(System.in);
System.out.println("Input String");
n = input.nextLine();
// probably wrong because a string can start as x(d))c(()...
for(int i = 0; i < n; i++)
{
if(n[i] != '(' || n[i] != ')' || n[i] != null || n[i] != " ") {
answer = 2 * (Integer.parseInt(n[i]); // how can i calculate if its a char
// i have to use mod % operator somewhere but I don't know where?
}
}
System.out.println("f(796) mod 997 = " + answer);
}
}
3 ответа
Вам может пригодиться следующий факт: количество строк из n пар сбалансированных скобок задается n-м каталонским числом, а его точное значение равно
(2n)! / (n! (n + 1)!)
Вы должны иметь возможность непосредственно вычислить это значение мода 997, используя подсказку о том, как продукты и суммы распределяются по модулю.
Надеюсь это поможет!
Вы должны сделать это:
public static void main (String[]args) {
String str = "((1+2)*(3+4))-5";
if(isValid(str)){
expandString(str);
}
}
public static boolean isValid(String s) {
int totalParenthesis = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
totalParenthesis++;
} else if (s.charAt(i) == ')') {
totalParenthesis--;
}
if (totalParenthesis < 0) {
return false;
}
}
if (totalParenthesis != 0) {
return false;
}
return true;
}
private static void expandString(String str) {
System.out.println("Called with : "+str);
if(!(str.contains("("))){
evalueMyExpresstion(str);
return;
}
String copyString=str;
int count=-1,positionOfOpen=0,positionOfClose=0;
for(Character character : str.toCharArray()) {
count++;
if(count==str.toCharArray().length){
evalueMyExpresstion(str);
return;
} else if(character.equals('(')) {
positionOfOpen=count+1;
} else if(character.equals(')')) {
positionOfClose=count;
copyString = str.substring(0, positionOfOpen - 1) + evalueMyExpresstion(
str.substring(positionOfOpen, positionOfClose)) + str.substring(positionOfClose + 1);
System.out.println("Call again with : "+copyString);
expandString(copyString);
return;
}
}
}
private static String evalueMyExpresstion(String str) {
System.out.println("operation : "+str);
String[] operation;
int returnVal =0;
if(str.contains("+")){
operation = str.split("\\+");
returnVal=Integer.parseInt(operation[0])+ Integer.parseInt(operation[1]);
System.out.println("+ val : "+returnVal);
return Integer.toString(returnVal);
} else if (str.contains("*")){
operation = str.split("\\*");
returnVal=Integer.parseInt(operation[0])* Integer.parseInt(operation[1]);
System.out.println("* val : "+returnVal);
return Integer.toString(returnVal);
} else if (str.contains("-")){
operation = str.split("\\-");
returnVal=Integer.parseInt(operation[0])- Integer.parseInt(operation[1]);
System.out.println("- val : "+returnVal);
return Integer.toString(returnVal);
}
System.out.println(str);
return Integer.toString(returnVal);
}
Вывод выглядит так:
Called with : ((1+2)*(3+4))-5
operation : 1+2
+ val : 3
Call again with : (3*(3+4))-5
Called with : (3*(3+4))-5
operation : 3+4
+ val : 7
Call again with : (3*7)-5
Called with : (3*7)-5
operation : 3*7
* val : 21
Call again with : 21-5
Called with : 21-5
operation : 21-5
- val : 16
Я до сих пор не совсем уверен, что именно вы спрашиваете, но проверить, являются ли круглые скобки допустимым размещением, можно с помощью следующего метода. Я использовал подобный, чтобы просмотреть сотни страниц, чтобы гарантировать, что все круглые скобки были закрыты должным образом в старые времена.
public static boolean isValid(String s) {
int openParens = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
// we found an open paren
openParens++;
} else if (s.charAt(i) == ')') {
// we can close a paren
openParens--;
}
if (openParens < 0) {
// we closed a paren but there was nothing to close!
return false;
}
}
if (openParens > 0) {
// we didn't close all parens!
return false;
}
// we did!
return true;
}