Dada una string str que consta de pares de paréntesis equilibrados , la tarea es calcular la puntuación de la string dada en función de las siguientes reglas:
- “ () ” tiene una puntuación de 1.
- “ xy ” tiene una puntuación de x + y , donde xey son pares individuales de paréntesis equilibrados.
- “ (x) ” tiene una puntuación el doble de x (es decir), 2 * puntuación de x .
Ejemplos:
Entrada: str = “()()”
Salida: 2
Explicación: Hay dos pares individuales de paréntesis balanceados “()()”. Por lo tanto, puntaje = puntaje de “()” + puntaje de “()” = 1 + 1 = 2Entrada: str = “(())”
Salida: 2
Explicación: Dado que la entrada tiene la forma “(x)”, la puntuación total = 2 * puntuación de “()” = 2 * 1 = 2
Enfoque: El problema se puede resolver usando Stack . La idea es iterar sobre los caracteres de la string . Para cada i -ésimo carácter, compruebe si el carácter es ‘(‘ o no. Si es cierto, inserte el carácter en la pila. De lo contrario, calcule la puntuación del paréntesis interior e inserte el doble de la puntuación en la pila. Siga los siguientes pasos para resolver el problema:
- Inicialice una pila para almacenar el carácter atravesado actual o la puntuación del paréntesis equilibrado interno.
- Iterar sobre los caracteres de la string , str . Para cada i -ésimo carácter verifique las siguientes condiciones:
- Si el carácter actual es ‘(‘ o no. Si se encuentra que es verdadero, entonces inserte el carácter actual en la pila .
- De lo contrario, compruebe si el elemento superior de la pila es ‘(‘ o no. Si es cierto, inserte «1» en la pila que representa la puntuación del paréntesis equilibrado interior.
- De lo contrario, duplique el elemento superior de la pila y coloque el valor obtenido en la pila .
- Finalmente, imprime la puntuación total obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <iostream> #include <stack> using namespace std; // Function to calculate // score of parentheses long long scoreOfParentheses(string S) { stack<string> s; // Stores index of // character of string int i = 0; // Stores total scores // obtained from the string long long ans = 0; // Iterate over characters // of the string while (i < S.length()) { // If s[i] is '(' if (S[i] == '(') s.push("("); else { // If top element of // stack is '(' if (s.top() == "(") { s.pop(); s.push("1"); } else { // Stores score of // inner parentheses long long count = 0; // Calculate score of // inner parentheses while (s.top() != "(") { // Update count count += stoi(s.top()); s.pop(); } // Pop from stack s.pop(); // Insert score of // inner parentheses s.push(to_string(2 * count)); } } // Update i i++; } // Calculate score // of the string while (!s.empty()) { // Update ans ans += stoi(s.top()); s.pop(); } return ans; } // Driver Code int main() { string S1 = "(()(()))"; cout << scoreOfParentheses(S1) << endl; return 0; }
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to calculate // score of parentheses static long scoreOfParentheses(String S) { Stack<String> s = new Stack<>(); // Stores index of // character of String int i = 0; // Stores total scores // obtained from the String long ans = 0; // Iterate over characters // of the String while (i < S.length()) { // If s[i] is '(' if (S.charAt(i) == '(') s.add("("); else { // If top element of // stack is '(' if (s.peek() == "(") { s.pop(); s.add("1"); } else { // Stores score of // inner parentheses long count = 0; // Calculate score of // inner parentheses while (s.peek() != "(") { // Update count count += Integer.parseInt(s.peek()); s.pop(); } // Pop from stack s.pop(); // Insert score of // inner parentheses s.add(String.valueOf(2 * count)); } } // Update i i++; } // Calculate score // of the String while (!s.isEmpty()) { // Update ans ans += Integer.parseInt(s.peek()); s.pop(); } return ans; } // Driver Code public static void main(String[] args) { String S1 = "(()(()))"; System.out.print(scoreOfParentheses(S1) +"\n"); } } // This code is contributed by 29AjayKumar.
Python3
# Python3 program to implement # the above approach # Function to calculate # score of parentheses def scoreOfParentheses(S): s = [] # Stores index of # character of string i = 0 # Stores total scores # obtained from the string ans = 0 # Iterate over characters # of the string while (i < len(S)): # If s[i] is '(' if (S[i] == '('): s.append("(") else: # If top element of # stack is '(' if (s[-1] == "("): s.pop() s.append("1") else: # Stores score of # inner parentheses count = 0 # Calculate score of # inner parentheses while (s[-1] != "("): # Update count count += int(s[-1]) s.pop() # Pop from stack s.pop() # Insert score of # inner parentheses s.append(str(2 * count)) # Update i i += 1 # Calculate score # of the string while len(s) > 0: # Update ans ans += int(s[-1]) s.pop() return ans # Driver Code if __name__ == '__main__': S1 = "(()(()))" print(scoreOfParentheses(S1)) # This code is contributed by mohit kumar 29
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to calculate // score of parentheses static long scoreOfParentheses(String S) { Stack<String> s = new Stack<String>(); // Stores index of // character of String int i = 0; // Stores total scores // obtained from the String long ans = 0; // Iterate over characters // of the String while (i < S.Length) { // If s[i] is '(' if (S[i] == '(') s.Push("("); else { // If top element of // stack is '(' if (s.Peek() == "(") { s.Pop(); s.Push("1"); } else { // Stores score of // inner parentheses long count = 0; // Calculate score of // inner parentheses while (s.Peek() != "(") { // Update count count += Int32.Parse(s.Peek()); s.Pop(); } // Pop from stack s.Pop(); // Insert score of // inner parentheses s.Push(String.Join("", 2 * count)); } } // Update i i++; } // Calculate score // of the String while (s.Count != 0) { // Update ans ans += Int32.Parse(s.Peek()); s.Pop(); } return ans; } // Driver Code public static void Main(String[] args) { String S1 = "(()(()))"; Console.Write(scoreOfParentheses(S1) +"\n"); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to implement // the above approach // Function to calculate // score of parentheses function scoreOfParentheses(S) { var s = []; // Stores index of // character of string var i = 0; // Stores total scores // obtained from the string var ans = 0; // Iterate over characters // of the string while (i < S.length) { // If s[i] is '(' if (S[i] == '(') s.push("("); else { // If top element of // stack is '(' if (s[s.length-1] == "(") { s.pop(); s.push("1"); } else { // Stores score of // inner parentheses var count = 0; // Calculate score of // inner parentheses while (s[s.length-1] != "(") { // Update count count += parseInt(s[s.length-1]); s.pop(); } // Pop from stack s.pop(); // Insert score of // inner parentheses s.push((2 * count).toString()); } } // Update i i++; } // Calculate score // of the string while (s.length!=0) { // Update ans ans += parseInt(s[s.length-1]); s.pop(); } return ans; } // Driver Code var S1 = "(()(()))"; document.write( scoreOfParentheses(S1)); </script>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rahulagarwal14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA