La siguiente expresión de sufijo con operandos de un solo dígito se evalúa mediante una pila:
8 2 3 ^ / 2 3 * + 5 1 * -
Tenga en cuenta que ^ es el operador de exponenciación. Los dos elementos superiores de la pila después de evaluar el primer * son:
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5
Respuesta: (A)
Explicación: El algoritmo para evaluar cualquier expresión de sufijo es bastante sencilla:
1. While there are input tokens left o Read the next token from input. o If the token is a value + Push it onto the stack. o Otherwise, the token is an operator (operator here includes both operators, and functions). * It is known a priori that the operator takes n arguments. * If there are fewer than n values on the stack (Error) The user has not input sufficient values in the expression. * Else, Pop the top n values from the stack. * Evaluate the operator, with the values as arguments. * Push the returned results, if any, back onto the stack. 2. If there is only one value in the stack o That value is the result of the calculation. 3. If there are more values in the stack o (Error) The user input has too many values.
Fuente del algoritmo: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithm
Ejecutemos el algoritmo anterior para la expresión dada.
Los primeros tres tokens son valores, por lo que simplemente se empujan. Después de empujar 8, 2 y 3, la pila es la siguiente
8, 2, 3
Cuando se lee ^, se abren los dos primeros y se calcula la potencia (2^3)
8, 8
Cuando se lee /, se abren los dos primeros y se realiza la división (8/8)
1
Los siguientes dos tokens son valores, por lo que simplemente se empujan. Después de empujar 2 y 3, la pila es la siguiente
1, 2, 3
Cuando aparece *, se abren los dos primeros y se realiza la multiplicación.
1, 6
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA