Evaluando una expresión aritmética completamente paréntesizada -- ++ campo con programming-challenge campo con recursion campo con time-limit-exceeded campo con math-expression-eval camp codereview Relacionados El problema

Evaluating a completely parenthesized arithmetic expression


5
vote

problema

Español

Intenté resolver el siguiente problema en un desafío de programación, pero el veredicto fue Límite de tiempo excedido .

Expresión completamente paréntesizada

Escriba un programa que lea una expresión completamente paréntesizada, y Imprime el resultado de evaluarlo. Los tres posibles operadores son Suma, sustracción y multiplicación. Los operandos son números naturales. entre 0 y 9 (ambos incluidos).

entrada

La entrada tiene una expresión completamente paréntesizada. Es decir, paréntesis Siempre aparecen alrededor de subexpresiones que no son dígisiones. Por ejemplo, la expresión 4 + 3 se escribiría

( 4 + 3 )

La expresión 8 * (4 + 3) se escribiría

( 8 * ( 4 + 3 ) )

La expresión Bootstrap.php0 se escribiría

Bootstrap.php1

Salida

Imprima una línea con un número entero: el resultado de evaluar el expresión dada.

(Fuente: https://jutge.org/problems/p45102_en/statement ) < / p>

Algunos de los casos de prueba públicos fueron (cada línea es un caso de prueba diferente):

  Bootstrap.php2  

Este es mi código, que aprobó todos los casos de prueba pública, pero no los privados. Pido su ayuda para encontrar el cuello de botella de mi programa.

  Bootstrap.php3  
Original en ingles

I tried to solve the following problem in a programming challenge, but the verdict was time limit exceeded.

Completely parenthesized expression

Write a program that reads a completely parenthesized expression, and prints the result of evaluating it. The three possible operators are sum, substraction and multiplication. The operands are natural numbers between 0 and 9 (both included).

Input

Input has a completely parenthesized expression. That is, parentheses always appear around subexpressions that are not digits. For instance, the expression 4 + 3 would be written

( 4 + 3 )

The expression 8 * (4 + 3) would be written

( 8 * ( 4 + 3 ) )

The expression (2 xe2x88x92 8) * (4 + 3) would be written

((2-8)*(4+3))

Output

Print a line with an integer number: the result of evaluating the given expression.

(Source: https://jutge.org/problems/P45102_en/statement)

Some of the public test cases were (each line is a different test case):

9 ( 3 + 4 ) ( 8 * ( 4 + 3 ) ) ( ( 2 - 8 ) * ( 4 + 3 ) ) ( ( 3 * 2 ) + 1 ) 

This is my code, which passed every public test cases, but not the private ones. I ask your help in order to find the bottleneck of my program.

#include <iostream> #include <sstream>  using std::string; using std::cin; using std::cout;  /**  * Returns the evaluation of a completely parenthesed expression.  *   * Preconditions:  *     * 0 <= i <= j < expr.size()-1.  *     * expr is a completely parenthesed expression.  *   * Postcondition: returns the evaluation of expr[i..j].  */  int evaluate(const string& expr, int i, int j) {     // Skip leading blanks     while (expr[i] == ' ') {         ++i;     }     while (expr[j] == ' ') {         --j;     }      // Base case     if (i == j) {         return expr[i] - '0';     }     // Recursive case     else {         // Skip first and last parentheses         ++i;         --j;         int open_parentheses = 0;         int end_i = i;         // Loop invariant:         //     * expr[i..end_i) is part of the first subexpression of expr[i..j]         //     * open_parentheses is the balance of opened and closed parentheses of expr[i..end_i)         while (open_parentheses > 0 || (expr[end_i] != '+' && expr[end_i] != '-' && expr[end_i] != '*')) {             if (expr[end_i] == '(') {                 ++open_parentheses;             }             else if (expr[end_i] == ')') {                 --open_parentheses;             }             ++end_i;         }         // Loop ending: expr[end_i] is the 'main' operation of expr[i..j]          char operation = expr[end_i];          // By induction hypothesis,         //     evaluate(expr, i, end_i - 1)          // and         //     evaluate(expr, end_i + 1, j)         // return the values of the first and the second subexpression of expr[i..j]          if (operation == '+') {             return evaluate(expr, i, end_i - 1) + evaluate(expr, end_i + 1, j);         } else if (operation == '-') {             return evaluate(expr, i, end_i - 1) - evaluate(expr, end_i + 1, j);         } else {             int first_expression = evaluate(expr, i, end_i - 1);             // Multiplication shortcut             if (first_expression == 0) {                 return 0;             } else {                 return first_expression * evaluate(expr, end_i + 1, j);                }         }     } }  int main() {     string expr;     getline(cin, expr);     cout << evaluate(expr, 0, expr.size() - 1) << "\n"; } 
              

Lista de respuestas

4
 
vote

iteradores
El int i y int j son parámetros innecesarios en CopyArbitMain0 . La clase de cadena es una clase de contenedor estándar. Las clases de contenedores estándar proporcionan el CopyArbitMain1 y CopyArbitMain2 Funciones que proporcionan a los iteradores al primer elemento y el último elemento del contenedor. Esta Pregunta de StackOverFlow.com Destaca por qué los iteradores son buenos.

Esta Pregunta de StackOverFlow.com proporciona un posible ejemplo para encontrar el último carácter para procesar.

El uso de iteradores será más rápido que usar la indexación por entero. En C ++ 11 o más tarde el siguiente bucle adelantará el iterador hasta que los caracteres espaciales no blancos se encuentren en la cadena.

  CopyArbitMain3  

Utilice funciones estándar C ++ para verificar el espacio en blanco En el ejemplo anterior CopyArbitMain4 , esto verifica todo el espacio en blanco, no solo el espacio para que se comprueba Tabs, espacios y nuevas líneas. Consultela isspace para obtener información sobre cómo usarlo.

Reducir la complejidad del código
No hay razón para tener la cláusula MOSS para CopyArbitMain5 , el código en la cláusula MOSS puede estar afuera debido a la devolución en la porción si entonces.

 

Use Iterators
The int i and int j are unnecessary parameters in int evaluate(const std::string& expr, int i, int j). The string class is a standard container class. Standard container classes provide the begin() and end() functions that provide iterators to the first element and the last element of the container. This StackOverflow.com Question highlights why iterators are good.

This StackOverflow.com question provides a possible example for finding the last character to process.

Using iterators will be faster than using indexing by integer. In C++11 or later the following loop will advance the iterator until non-white space characters are found in the string.

for (auto CharInExperession : exper) {     if (!isspace(*CharInExperssion)) {         break;     } } 

Use Standard C++ functions to check for white space In the example above isspace() is used, this checks for all white space, not just space so it checks for tabs, spaces and new lines. See isspace for information on how to use it.

Reduce the Complexity of the Code
There is no reason to have the else clause for if(i == j) {, the code in the else clause can be out-dented because of the return in the if-then portion.

 
 
1
 
vote
vote
La mejor respuesta
 

Tengo un veredicto con el siguiente código.

Algunos comentarios:

  • movido de CopyArbitMain6 s a CopyArbitMain7 s. La ineficiencia estaba aquí.
  • no se mudó a CopyArbitMain8 . Estoy seguro de que es una mejor opción si la eficiencia no lo es importante, pero falló en términos de eficiencia.
  • He simplificado el bloque de decisión de recursión.

El código:

  CopyArbitMain9  
 

I got a pass verdict with the following code.

Some comments:

  • Moved from ints to string::const_iterators. Inefficiency was here.
  • Didn't move to isspace. I'm sure it is a better option if efficiency is not that important, but failed in efficiency terms.
  • I've simplified the recursion decision block.

The code:

#include <iostream> #include <sstream>  using std::string; using std::cin; using std::cout;  typedef string::const_iterator it;   /**  * Returns the evaluation of a completely parenthesed expression.  *   * Preconditions:  *     * i and j point to characters of expr.  *     * expr is a completely parenthesed expression.  *   * Postcondition: returns the evaluation of expr[i..j].  */ int evaluate(const string& expr, it i, it j) {     // Skip leading blanks     while (*i == ' ') {         ++i;     }     while (*j == ' ') {         --j;     }      // Base case     if (i == j) {         return *i - '0';     }      // Recursive case     // Skip first and last parentheses     ++i;     --j;     int open_parentheses = 0;     it end_i = i;     // Loop invariant:     //     * expr[i..end_i) is part of the first subexpression of expr[i..j]     //     * open_parentheses is the balance of opened and closed parentheses of expr[i..end_i)     while (open_parentheses > 0 || (*end_i != '+' && *end_i != '-' && *end_i != '*')) {         if (*end_i == '(') {             ++open_parentheses;         }         else if (*end_i == ')') {             --open_parentheses;         }         ++end_i;     }     // Loop ending: *end_i is the 'main' operation of expr[i..j]      char operation = *end_i;      it begin_j = end_i;     ++begin_j;     --end_i;     int first = evaluate(expr, i, end_i);     if (operation == '*') {         if (first == 0) {             return 0;         } else {             int second = evaluate(expr, begin_j, j);             return first * second;            }     } else {         int second = evaluate(expr, begin_j, j);         if (operation == '+') {             return first + second;         } else {             return first - second;         }     } }   int main() {     string expr;     getline(cin, expr);     it i, j;     i = expr.begin();     j = expr.end();     --j;     cout << evaluate(expr, i, j) << "\n"; } 
 
 

Relacionados problema

8  Codewars Evaluador de expresión matemática  ( Codewars mathematical expresion evaluator ) 
Recientemente escribí el siguiente código para un Codewars.com Kata para evaluar las expresiones matemáticas . He estado escribiendo Ruby durante años, pero ...

5  Calculadora de derivados algebraica estándar  ( Standard algebraic derivative calculator ) 
Tuve alguna dificultad con este problema, así que estoy seguro de que hay una mejor manera. Aquí está la pregunta de SICP : ejercicio 2.58 Supongamos ...

2  Expresión de infijo (con números negativos) a Postfix  ( Infix expression with negative numbers to postfix ) 
Estoy escribiendo una clase para evaluar una expresión aritmética, ya que ahora mi clase puede convertir una expresión de infijo en PostFix, todavía no admite...

6  Programa de Convertidor de Infix a Postfix  ( Infix to postfix converter program ) 
Esta es mi tarea. Amablemente ayúdame a verificarlo? Las instrucciones son: Implementar una expresión de infIX en el convertidor de expresión postfix. De...

2  Verificación de expresiones matemáticas  ( Verifying mathematical expressions ) 
Esta es una parte de mi programa de calculadora. Tengo que verificar si la entrada ingresada por el usuario es una expresión matemática válida. El primer prog...

1  Evaluando una expresión aritmética de un árbol binario  ( Evaluating an arithmetic expression from a binary tree ) 
Digamos que tengo un árbol binario que se ve + 2 * 5 8 He escrito una función para atravesar el inicio para resolverl...

3  Calculadora de RPN de NASM  ( Nasm rpn calculator ) 
He estado aprendiendo ensamblaje en los últimos días, y he hecho una simple calculadora RPN. Aquí está la lógica principal del programa, excluyendo las func...

3  Análisis de expresión (solo operadores aritméticos)  ( Expression parsing arithmetic operators only ) 
Como un proyecto de auto-aprendizaje, escribí un analizador de expresión utilizando el algoritmo de la derivación del patio en JavaScript. Es una parte más gr...

1  Parser Ecuación + Solver  ( Equation parser solver ) 
Aquí hay un analizador de la ecuación que acabo de escribir. Mi enfoque fue la legibilidad y la perspectiva de agregar nuevas características en el futuro. Co...

3  La calculadora recursiva basada en RPN-STACK necesita TuneUp  ( Rpn stack based recursive calculator needs tuneup ) 
Esta función toma una serie de cuerdas y números y la procesa recursivamente como un tipo de "programa de cálculo". La estructura se basa en la notación de po...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos