В поисках сбалансированной скобки, включающей математику

Question

Я пытался решить этот вопрос в течение последних нескольких часов, и я просто не понимаю его. Я знаю, что для этого нужно какое-то математическое вычисление, но я не знаю, как точно его вычислить. Я знаю, что этот код не имеет смысла, потому что я полностью потерян, я был бы признателен за любые подсказки или помощь для этого, чтобы помочь мне приблизиться к решению.

Я спросил своего профессора, и он намекнул, что это похоже на перестановку / комбинацию с использованием алфавита, например 26^3, для 3 различных комбинаций, но это мне не сильно помогло.

Что я знаю:

1. Есть 796 символов для ввода данных в строке, и я должен найти ВСЕ возможные способы, которыми 796 символов могут быть в форме сбалансированных скобок.

2. Поскольку он должен начинаться с '(' и заканчиваться на ')', для каждого случая должно быть 2 скобки. Так что это может быть '()()(xc)(cvs)'. Таким образом, это означает, что математический расчет должен включать 2*(что-то) на символ (ы), так как он должен быть сбалансирован.

3. Мне нужно использовать оператор остаток (%), чтобы рекурсивно найти каждый случай, но как мне это сделать, когда я беру char в не int?

Что я не знаю:

1. Как я буду анализировать каждый случай? Не займет ли это много времени или много кода без простой формулы для расчета ввода?

2. Мне нужно много 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);

    }
 }

Answer 1

Вам может пригодиться следующий факт: количество строк из n пар сбалансированных скобок задается n-м каталонским числом, а его точное значение равно

(2n)! / (n! (n + 1)!)

Вы должны иметь возможность непосредственно вычислить это значение мода 997, используя подсказку о том, как продукты и суммы распределяются по модулю.

Надеюсь это поможет!

Answer 2

Вы должны сделать это:

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

Answer 3

Я до сих пор не совсем уверен, что именно вы спрашиваете, но проверить, являются ли круглые скобки допустимым размещением, можно с помощью следующего метода. Я использовал подобный, чтобы просмотреть сотни страниц, чтобы гарантировать, что все круглые скобки были закрыты должным образом в старые времена.

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