Dada una string str que contiene pares de paréntesis equilibrados, la tarea es calcular la puntuación de la string dada según las reglas dadas:
- “()” 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), la puntuación es 2 * puntuación de x.
Ejemplos:
Entrada: str = “()()”
Salida: 2
Explicación:
Aquí la entrada tiene la forma “xy”, lo que hace que la puntuación total = puntuación de x + puntuación de y
y, por lo tanto, puntuación = 1 + 1 = 2Entrada: str = “(())”
Salida: 2
Explicación:
Aquí la entrada tiene la forma “(x)”, lo que hace que la puntuación total = 2 * puntuación de x
y, por lo tanto, puntuación = 2 * 1 = 2Entrada: str = “(()()())”
Salida: 6
Explicación:
Aquí la entrada tiene la forma “(xyz)”, lo que hace que la puntuación total = 2 * (puntuación de x +
puntuación de y + puntuación de z ) y por lo tanto 2*(1 + 1 + 1) = 6
Enfoque: la idea es usar una estructura de datos de árbol para resolver este problema junto con Recursion .
- El Node raíz de nuestra estructura de árbol representará el par más externo de nuestros paréntesis de entrada.
- Por cada par de paréntesis equilibrados incluidos dentro de los paréntesis más externos, agregaremos un hijo a nuestro Node raíz.
- Este proceso de declarar un hijo a un Node raíz será recursivo y, por lo tanto, creará un Node en nuestra estructura de árbol para cada par de paréntesis equilibrados en una jerarquía.
- Cada par de paréntesis equilibrados se considerará como el más externo (recursivamente) y generará un Node y, por lo tanto, nos permitirá calcular la puntuación.
- Al calcular el puntaje, cada Node hoja de nuestro árbol se considerará con un puntaje de 1 y para obtener el puntaje de su respectivo Node raíz, debemos sumar los puntajes de cada Node secundario y duplicar ese agregado.
- El siguiente diagrama muestra la estructura recursiva del árbol generado y comenzamos desde abajo para calcular los puntajes en cada nivel hasta llegar a los paréntesis finales más externos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the score of
// parentheses using Tree
#include <iostream>
#include <vector>
using namespace std;
// Customized tree class or struct,
// contains all required methods.
class TreeNode {
TreeNode* parent = NULL;
vector<TreeNode*> children;
public:
// Function to add a child into
// the list of children
void addChild(TreeNode* node)
{
children.push_back(node);
}
// Function to change the parent
// pointer to the node passed
void setParent(TreeNode* node)
{
parent = node;
}
// Function to return the parent
// of the current node
TreeNode* getParent()
{
return parent;
}
// Function to compute the score recursively.
int computeScore()
{
// Base case
if (children.size() == 0)
return 1;
int res = 0;
// Adds scores of all children
for (TreeNode* curr : children)
res += curr->computeScore();
if (parent == NULL)
return res;
else
return 2 * res;
}
};
// Function to create the tree structure
TreeNode* computeTree(string s)
{
TreeNode* current = new TreeNode();
TreeNode* root = current;
// Creating a node for every "()"
for (int i = 0; i < s.size(); i++) {
// If we find "(" we add a node as
// a child
if (s[i] == '(') {
TreeNode* child = new TreeNode();
child->setParent(current);
current->addChild(child);
current = child;
}
// On finding ")" which confirms that
// a pair is closed, we go back
// to the parent
else {
current = current->getParent();
}
}
return root;
}
// Driver code
int main()
{
string s = "(()(()))";
// Generating the tree
TreeNode* root = computeTree(s);
// Computing the score
cout << root->computeScore();
return 0;
}
Java
// Java program to find the score of
// parentheses using Tree
import java.util.*;
public class Main
{
// Customized tree class or struct,
// contains all required methods.
static class TreeNode {
public TreeNode parent = null;
public Vector<TreeNode> children = new Vector<TreeNode>();
// Function to add a child into
// the list of children
public void addChild(TreeNode node)
{
children.add(node);
}
// Function to change the parent
// pointer to the node passed
public void setParent(TreeNode node)
{
parent = node;
}
// Function to return the parent
// of the current node
public TreeNode getParent()
{
return parent;
}
// Function to compute the score
// recursively.
public int computeScore()
{
// Base case
if (children.size() == 0)
return 1;
int res = 0;
// Adds scores of all children
for(TreeNode curr : children)
res += curr.computeScore();
if (parent == null)
return res;
else
return 2 * res;
}
}
// Function to create the tree structure
static TreeNode computeTree(String s)
{
TreeNode current = new TreeNode();
TreeNode root = current;
// Creating a node for every "()"
for(int i = 0; i < s.length(); i++)
{
// If we find "(" we add a node as
// a child
if (s.charAt(i) == '(')
{
TreeNode child = new TreeNode();
child.setParent(current);
current.addChild(child);
current = child;
}
// On finding ")" which confirms that
// a pair is closed, we go back
// to the parent
else
{
current = current.getParent();
}
}
return root;
}
public static void main(String[] args) {
String s = "(()(()))";
// Generating the tree
TreeNode root = computeTree(s);
// Computing the score
System.out.print(root.computeScore());
}
}
// This code is contributed by suresh07.
Python3
# Python3 program to find the score of
# parentheses using Tree
# Customized tree class or struct,
# contains all required methods.
class TreeNode:
def __init__(self):
self.parent = None
self.children = []
# Function to add a child into
# the list of children
def addChild(self, node):
self.children.append(node);
# Function to change the parent
# pointer to the node passed
def setParent(self, node):
self.parent = node;
# Function to return the parent
# of the current node
def getParent(self):
return self.parent;
# Function to compute the score recursively.
def computeScore(self):
# Base case
if (len(self.children) == 0):
return 1;
res = 0;
# Adds scores of all children
for curr in self.children:
res += curr.computeScore();
if (self.parent == None):
return res;
else:
return 2 * res;
# Function to create the tree structure
def computeTree(s):
current = TreeNode();
root = current;
# Creating a node for every "()"
for i in range(len(s)):
# If we find "(" we add a node as
# a child
if (s[i] == '('):
child = TreeNode();
child.setParent(current);
current.addChild(child);
current = child;
# On finding ")" which confirms that
# a pair is closed, we go back
# to the parent
else:
current = current.getParent();
return root;
# Driver code
if __name__=='__main__':
s = "(()(()))";
# Generating the tree
root = computeTree(s);
# Computing the score
print(root.computeScore())
# This code is contributed by rutvik_56
C#
// C# program to find the score of
// parentheses using Tree
using System;
using System.Collections;
class GFG{
// Customized tree class or struct,
// contains all required methods.
class TreeNode
{
public TreeNode parent = null;
public ArrayList children = new ArrayList();
// Function to add a child into
// the list of children
public void addChild(TreeNode node)
{
children.Add(node);
}
// Function to change the parent
// pointer to the node passed
public void setParent(TreeNode node)
{
parent = node;
}
// Function to return the parent
// of the current node
public TreeNode getParent()
{
return parent;
}
// Function to compute the score
// recursively.
public int computeScore()
{
// Base case
if (children.Count == 0)
return 1;
int res = 0;
// Adds scores of all children
foreach(TreeNode curr in children)
res += curr.computeScore();
if (parent == null)
return res;
else
return 2 * res;
}
};
// Function to create the tree structure
static TreeNode computeTree(string s)
{
TreeNode current = new TreeNode();
TreeNode root = current;
// Creating a node for every "()"
for(int i = 0; i < s.Length; i++)
{
// If we find "(" we add a node as
// a child
if (s[i] == '(')
{
TreeNode child = new TreeNode();
child.setParent(current);
current.addChild(child);
current = child;
}
// On finding ")" which confirms that
// a pair is closed, we go back
// to the parent
else
{
current = current.getParent();
}
}
return root;
}
// Driver code
public static void Main()
{
string s = "(()(()))";
// Generating the tree
TreeNode root = computeTree(s);
// Computing the score
Console.Write(root.computeScore());
}
}
// This code is contributed by pratham76
Producción:
6
Complejidad de tiempo: O(N) , donde N es la longitud de la string de entrada.
Complejidad espacial: O(N) , donde N es la longitud de la string de entrada.
Publicación traducida automáticamente
Artículo escrito por si_shubham y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA