La notación polaca inversa es una notación posfija que, en términos de noción matemática, significa operadores que siguen a operandos. Tomemos un enunciado del problema para implementar RPN
Declaración del problema: la tarea es encontrar el valor de la expresión aritmética presente en la array usando operadores válidos como +, -, *, /. Cada operando puede ser un número entero u otra expresión.
Nota:
- La división entre dos números enteros debe truncar hacia cero.
- La expresión RPN dada siempre es válida. Eso significa que la expresión siempre se evaluará como un resultado y no habrá ninguna operación de división por cero.
Layman trabajando de RPN como se muestra
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Acercarse:
El enfoque básico para el problema es usar la pila.
- Accediendo a todos los elementos de la array, si el elemento no coincide con el carácter especial (‘+’, ‘-‘, ‘*’, ‘/’), empuje el elemento a la pila.
- Luego, cada vez que se encuentre el carácter especial, extraiga los primeros dos elementos de la pila y realice la acción y luego empuje el elemento para apilar nuevamente.
- Repita los dos procesos anteriores para todos los elementos de la array
- Por último, saque el elemento de la pila e imprima el resultado
Implementación:
Python3
# Python 3 code to evaluate reverse polish notation
"""
This code is contributed by Harshal Gupta
"""
# function to evaluate reverse polish notation
def evaluate(expression):
# splitting expression at whitespaces
expression = expression.split()
# stack
stack = []
# iterating expression
for ele in expression:
# ele is a number
if ele not in '/*+-':
stack.append(int(ele))
# ele is an operator
else:
# getting operands
right = stack.pop()
left = stack.pop()
# performing operation according to operator
if ele == '+':
stack.append(left + right)
elif ele == '-':
stack.append(left - right)
elif ele == '*':
stack.append(left * right)
elif ele == '/':
stack.append(int(left / right))
# return final answer.
return stack.pop()
# input expression
arr = "10 6 9 3 + -11 * / * 17 + 5 +"
# calling evaluate()
answer = evaluate(arr)
# printing final value of the expression
print(f"Value of given expression'{arr}' = {answer}")
C++
#include <bits/stdc++.h>
using namespace std;
int eval(vector<string>& A)
{
stack<int> st;
for (int i = 0; i < A.size(); i++) {
if (A[i] != "+" && A[i] != "-" && A[i] != "/"
&& A[i] != "*") {
st.push(stoi(A[i]));
continue;
}
else {
int b = st.top();
st.pop();
int a = st.top();
st.pop();
if (A[i] == "+")
st.push(a + b);
else if (A[i] == "-")
st.push(a - b);
else if (A[i] == "*")
st.push(a * b);
else
st.push(a / b);
}
}
return st.top();
}
int main()
{
vector<string> A
= { "10", "6", "9", "3", "+", "-11", "*",
"/", "*", "17", "+", "5", "+" };
int res = eval(A);
cout << res << endl;
}
Java
// Java Program to find the
// solution of the arithmetic
// using the stack
import java.io.*;
import java.util.*;
class solution {
public int stacky(String[] tokens)
{
// Initialize the stack and the variable
Stack<String> stack = new Stack<String>();
int x, y;
String result = "";
int get = 0;
String choice;
int value = 0;
String p = "";
// Iterating to the each character
// in the array of the string
for (int i = 0; i < tokens.length; i++) {
// If the character is not the special character
// ('+', '-' ,'*' , '/')
// then push the character to the stack
if (tokens[i] != "+" && tokens[i] != "-"
&& tokens[i] != "*" && tokens[i] != "/") {
stack.push(tokens[i]);
continue;
}
else {
// else if the character is the special
// character then use the switch method to
// perform the action
choice = tokens[i];
}
// Switch-Case
switch (choice) {
case "+":
// Performing the "+" operation by poping
// put the first two character
// and then again store back to the stack
x = Integer.parseInt(stack.pop());
y = Integer.parseInt(stack.pop());
value = x + y;
result = p + value;
stack.push(result);
break;
case "-":
// Performing the "-" operation by poping
// put the first two character
// and then again store back to the stack
x = Integer.parseInt(stack.pop());
y = Integer.parseInt(stack.pop());
value = y - x;
result = p + value;
stack.push(result);
break;
case "*":
// Performing the "*" operation
// by poping put the first two character
// and then again store back to the stack
x = Integer.parseInt(stack.pop());
y = Integer.parseInt(stack.pop());
value = x * y;
result = p + value;
stack.push(result);
break;
case "/":
// Performing the "/" operation by poping
// put the first two character
// and then again store back to the stack
x = Integer.parseInt(stack.pop());
y = Integer.parseInt(stack.pop());
value = y / x;
result = p + value;
stack.push(result);
break;
default:
continue;
}
}
// Method to convert the String to integer
return Integer.parseInt(stack.pop());
}
}
class GFG {
public static void main(String[] args)
{
// String Input
String[] s
= { "10", "6", "9", "3", "+", "-11", "*",
"/", "*", "17", "+", "5", "+" };
solution str = new solution();
int result = str.stacky(s);
System.out.println(result);
}
}
Producción
Value of given expression'10 6 9 3 + -11 * / * 17 + 5 +' = 22
Complejidad temporal: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA