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>
Producción:
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