Calcular la puntuación de paréntesis de una string dada

Dada la string str de longitud N , que consta de pares de paréntesis equilibrados, la tarea es calcular la puntuación de la string dada en función de las reglas dadas:

• “()” tiene una puntuación de 1 .
• “ab” tiene una puntuación de a + b , donde a y b son pares individuales de paréntesis equilibrados.
• “(a)” tiene una puntuación el doble de a ie, la puntuación es 2 * puntuación de a .

Ejemplos:

Entrada: str = “()()” 
Salida: 2 
Explicación: La string str tiene la forma “ab”, lo que hace que la puntuación total = (puntuación de a) + (puntuación de b) = 1 + 1 = 2.

Entrada: str = “(()(()))”
Salida: 6
Explicación: La string str tiene la forma “(a(b))” lo que hace que la puntuación total = 2 * ((puntuación de a) + 2 *(puntaje de b)) = 2*(1 + 2*(1)) = 6.

Enfoque basado en árboles : consulte la publicación anterior de este artículo para conocer el enfoque basado en árboles. 
Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Enfoque basado en la pila : la idea es atravesar la string y, mientras atraviesa la string str, si se encuentra el paréntesis ‘)’ , calcule la puntuación de este par de paréntesis. Siga los pasos a continuación para resolver el problema:

• Inicialice una pila, digamos S , para realizar un seguimiento de la puntuación e inicialmente inserte 0 en la pila .
• Recorra la string str usando la variable i y realice los siguientes pasos:
  • Si el valor de str[i] es igual a ‘(‘ , inserte 0 en la pila S .
  • De lo contrario, realice los siguientes pasos:
    • Almacene la parte superior de la pila S en una variable, digamos temp , y extraiga el elemento de la parte superior de la pila .
    • Si el valor de temp no es cero , entonces existen paréntesis internos. Agregue 2 * temp a la parte superior de la pila . De lo contrario, agregue 1 a la parte superior de la pila .
• Después de completar los pasos anteriores, imprima el valor de la parte superior de la pila como resultado.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the score
// of the parentheses using stack
void scoreOfParentheses(string s)
{
    // To keep track of the score
    stack<int> stack;
 
    // Initially, push 0 to stack
    stack.push(0);
 
    // Traverse the string s
    for (char c : s) {
 
        // If '(' is encountered,
        // then push 0 to stack
        if (c == '(')
            stack.push(0);
 
        // Otherwise
        else {
 
            // Balance the last '(', and store
            // the score of inner parentheses
            int tmp = stack.top();
            stack.pop();
 
            int val = 0;
 
            // If tmp is not zero, it means
            // inner parentheses exists
            if (tmp > 0)
                val = tmp * 2;
 
            // Otherwise, it means no
            // inner parentheses exists
            else
                val = 1;
 
            // Pass the score of this level
            // to parent parentheses
            stack.top() += val;
        }
    }
 
    // Print the score
    cout << stack.top();
}
 
// Driver Code
int main()
{
    string S = "(()(()))";
    scoreOfParentheses(S);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to calculate the score
  // of the parentheses using stack
  static void scoreOfParentheses(String s)
  {
     
    // To keep track of the score
    Stack<Integer> stack = new Stack<>();
 
    // Initially, push 0 to stack
    stack.push(0);
 
    // Traverse the string s
    for (char c : s.toCharArray()) {
 
      // If '(' is encountered,
      // then push 0 to stack
      if (c == '(')
        stack.push(0);
 
      // Otherwise
      else {
 
        // Balance the last '(', and store
        // the score of inner parentheses
        int tmp = stack.pop();
 
        int val = 0;
 
        // If tmp is not zero, it means
        // inner parentheses exists
        if (tmp > 0)
          val = tmp * 2;
 
        // Otherwise, it means no
        // inner parentheses exists
        else
          val = 1;
 
        // Pass the score of this level
        // to parent parentheses
        stack.push(stack.pop() + val);
      }
    }
 
    // Print the score
    System.out.println(stack.peek());
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    String S = "(()(()))";
 
    // Function call
    scoreOfParentheses(S);
  }
}
 
// This code is contributed by Kingash.

# Python 3 program for the above approach
 
# Function to calculate the score
# of the parentheses using stack
def scoreOfParentheses(s):
   
    # To keep track of the score
    stack = []
 
    # Initially, push 0 to stack
    stack.append(0)
 
    # Traverse the string s
    for c in s:
       
        # If '(' is encountered,
        # then push 0 to stack
        if (c == '('):
            stack.append(0)
 
        # Otherwise
        else:
           
            # Balance the last '(', and store
            # the score of inner parentheses
            tmp = stack[len(stack) - 1]
            stack = stack[:-1]
 
            val = 0
 
            # If tmp is not zero, it means
            # inner parentheses exists
            if (tmp > 0):
                val = tmp * 2
 
            # Otherwise, it means no
            # inner parentheses exists
            else:
                val = 1
 
            # Pass the score of this level
            # to parent parentheses
            stack[len(stack) - 1] += val
 
    # Print the score
    print(stack[len(stack) - 1])
 
# Driver Code
if __name__ == '__main__':
    S = "(()(()))"
    scoreOfParentheses(S)
     
    # This code is contributed by bgangwar59.

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
  // Function to calculate the score
  // of the parentheses using stack
  static void scoreOfParentheses(String s)
  {
     
    // To keep track of the score
    Stack<int> stack = new Stack<int>();
 
    // Initially, push 0 to stack
    stack.Push(0);
 
    // Traverse the string s
    foreach (char c in s.ToCharArray()) {
 
      // If '(' is encountered,
      // then push 0 to stack
      if (c == '(')
        stack.Push(0);
 
      // Otherwise
      else {
 
        // Balance the last '(', and store
        // the score of inner parentheses
        int tmp = stack.Pop();
 
        int val = 0;
 
        // If tmp is not zero, it means
        // inner parentheses exists
        if (tmp > 0)
          val = tmp * 2;
 
        // Otherwise, it means no
        // inner parentheses exists
        else
          val = 1;
 
        // Pass the score of this level
        // to parent parentheses
        stack.Push(stack.Pop() + val);
      }
    }
 
    // Print the score
    Console.WriteLine(stack.Peek());
  }
 
  // Driver code
  public static void Main(String[] args)
  {
 
    String S = "(()(()))";
 
    // Function call
    scoreOfParentheses(S);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program for the above approach
 
// Function to calculate the score
// of the parentheses using stack
function scoreOfParentheses(s)
{
    // To keep track of the score
    var stack = [];
 
    // Initially, push 0 to stack
    stack.push(0);
 
    // Traverse the string s
    s.split('').forEach(c => {
         
 
        // If '(' is encountered,
        // then push 0 to stack
        if (c == '(')
            stack.push(0);
 
        // Otherwise
        else {
 
            // Balance the last '(', and store
            // the score of inner parentheses
            var tmp = stack[stack.length-1];
            stack.pop();
 
            var val = 0;
 
            // If tmp is not zero, it means
            // inner parentheses exists
            if (tmp > 0)
                val = tmp * 2;
 
            // Otherwise, it means no
            // inner parentheses exists
            else
                val = 1;
 
            // Pass the score of this level
            // to parent parentheses
            stack[stack.length-1] += val;
        }
    });
 
    // Print the score
    document.write( stack[stack.length-1]);
}
 
// Driver Code
var S = "(()(()))";
scoreOfParentheses(S);
 
 
</script>

6

Complejidad temporal: O(N)
Espacio auxiliar: O(N)