Las expresiones de prefijo y sufijo se pueden evaluar más rápido que una expresión de infijo. Esto se debe a que no necesitamos procesar ningún paréntesis ni seguir la regla de precedencia de operadores. En las expresiones de postfijo y prefijo, el operador que esté antes se evaluará primero, independientemente de su prioridad. Además, no hay corchetes en estas expresiones. Siempre que podamos garantizar que se utiliza una expresión válida de prefijo o posfijo, se puede evaluar correctamente.
Podemos convertir infijos a postfijos y podemos convertir infijos a prefijos.
En este artículo, discutiremos cómo evaluar una expresión escrita en notación de prefijo. El método es similar a evaluar una expresión de sufijo. Por favor, lea Evaluación de Expresión de Postfijo para saber cómo evaluar expresiones de postfijo
Algoritmo:
EVALUATE_PREFIX(STRING)
Step 1: Put a pointer P at the end of the end
Step 2: If character at P is an operand push it to Stack
Step 3: If the character at P is an operator pop two
elements from the Stack. Operate on these elements
according to the operator, and push the result
back to the Stack
Step 4: Decrement P by 1 and go to Step 2 as long as there
are characters left to be scanned in the expression.
Step 5: The Result is stored at the top of the Stack,
return it
Step 6: End
Ejemplo para demostrar el funcionamiento del algoritmo.
Expression: +9*26
Character | Stack | Explanation
Scanned | (Front to |
| Back) |
-------------------------------------------
6 6 6 is an operand,
push to Stack
2 6 2 2 is an operand,
push to Stack
* 12 (6*2) * is an operator,
pop 6 and 2, multiply
them and push result
to Stack
9 12 9 9 is an operand, push
to Stack
+ 21 (12+9) + is an operator, pop
12 and 9 add them and
push result to Stack
Result: 21
Ejemplos:
Input : -+8/632 Output : 8 Input : -+7*45+20 Output : 25
Complejidad El algoritmo tiene una complejidad lineal ya que escaneamos la expresión una vez y realizamos como máximo operaciones de inserción y extracción O(N) que toman un tiempo constante.
La implementación del algoritmo se da a continuación.
Implementación:
C++
// C++ program to evaluate a prefix expression.
#include <bits/stdc++.h>
using namespace std;
bool isOperand(char c)
{
// If the character is a digit then it must
// be an operand
return isdigit(c);
}
double evaluatePrefix(string exprsn)
{
stack<double> Stack;
for (int j = exprsn.size() - 1; j >= 0; j--) {
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isOperand(exprsn[j]))
Stack.push(exprsn[j] - '0');
else {
// Operator encountered
// Pop two elements from Stack
double o1 = Stack.top();
Stack.pop();
double o2 = Stack.top();
Stack.pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn[j]) {
case '+':
Stack.push(o1 + o2);
break;
case '-':
Stack.push(o1 - o2);
break;
case '*':
Stack.push(o1 * o2);
break;
case '/':
Stack.push(o1 / o2);
break;
}
}
}
return Stack.top();
}
// Driver code
int main()
{
string exprsn = "+9*26";
cout << evaluatePrefix(exprsn) << endl;
return 0;
}
Java
// Java program to evaluate
// a prefix expression.
import java.io.*;
import java.util.*;
class GFG {
static Boolean isOperand(char c)
{
// If the character is a digit
// then it must be an operand
if (c >= 48 && c <= 57)
return true;
else
return false;
}
static double evaluatePrefix(String exprsn)
{
Stack<Double> Stack = new Stack<Double>();
for (int j = exprsn.length() - 1; j >= 0; j--) {
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isOperand(exprsn.charAt(j)))
Stack.push((double)(exprsn.charAt(j) - 48));
else {
// Operator encountered
// Pop two elements from Stack
double o1 = Stack.peek();
Stack.pop();
double o2 = Stack.peek();
Stack.pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn.charAt(j)) {
case '+':
Stack.push(o1 + o2);
break;
case '-':
Stack.push(o1 - o2);
break;
case '*':
Stack.push(o1 * o2);
break;
case '/':
Stack.push(o1 / o2);
break;
}
}
}
return Stack.peek();
}
/* Driver program to test above function */
public static void main(String[] args)
{
String exprsn = "+9*26";
System.out.println(evaluatePrefix(exprsn));
}
}
// This code is contributed by Gitanjali
Python3
""" Python3 program to evaluate a prefix expression. """ def is_operand(c): """ Return True if the given char c is an operand, e.g. it is a number """ return c.isdigit() def evaluate(expression): """ Evaluate a given expression in prefix notation. Asserts that the given expression is valid. """ stack = [] # iterate over the string in reverse order for c in expression[::-1]: # push operand to stack if is_operand(c): stack.append(int(c)) else: # pop values from stack can calculate the result # push the result onto the stack again o1 = stack.pop() o2 = stack.pop() if c == '+': stack.append(o1 + o2) elif c == '-': stack.append(o1 - o2) elif c == '*': stack.append(o1 * o2) elif c == '/': stack.append(o1 / o2) return stack.pop() # Driver code if __name__ == "__main__": test_expression = "+9*26" print(evaluate(test_expression)) # This code is contributed by Leon Morten Richter (GitHub: M0r13n)
C#
// C# program to evaluate
// a prefix expression.
using System;
using System.Collections.Generic;
class GFG {
static Boolean isOperand(char c)
{
// If the character is a digit
// then it must be an operand
if (c >= 48 && c <= 57)
return true;
else
return false;
}
static double evaluatePrefix(String exprsn)
{
Stack<Double> Stack = new Stack<Double>();
for (int j = exprsn.Length - 1; j >= 0; j--) {
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isOperand(exprsn[j]))
Stack.Push((double)(exprsn[j] - 48));
else {
// Operator encountered
// Pop two elements from Stack
double o1 = Stack.Peek();
Stack.Pop();
double o2 = Stack.Peek();
Stack.Pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn[j]) {
case '+':
Stack.Push(o1 + o2);
break;
case '-':
Stack.Push(o1 - o2);
break;
case '*':
Stack.Push(o1 * o2);
break;
case '/':
Stack.Push(o1 / o2);
break;
}
}
}
return Stack.Peek();
}
/* Driver code */
public static void Main(String[] args)
{
String exprsn = "+9*26";
Console.WriteLine(evaluatePrefix(exprsn));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to evaluate a prefix expression.
function isOperand(c)
{
// If the character is a digit
// then it must be an operand
if (c.charCodeAt() >= 48 && c.charCodeAt() <= 57)
return true;
else
return false;
}
function evaluatePrefix(exprsn)
{
let Stack = [];
for (let j = exprsn.length - 1; j >= 0; j--) {
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isOperand(exprsn[j]))
Stack.push((exprsn[j].charCodeAt() - 48));
else {
// Operator encountered
// Pop two elements from Stack
let o1 = Stack[Stack.length - 1];
Stack.pop();
let o2 = Stack[Stack.length - 1];
Stack.pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn[j]) {
case '+':
Stack.push(o1 + o2);
break;
case '-':
Stack.push(o1 - o2);
break;
case '*':
Stack.push(o1 * o2);
break;
case '/':
Stack.push(o1 / o2);
break;
}
}
}
return Stack[Stack.length - 1];
}
let exprsn = "+9*26";
document.write(evaluatePrefix(exprsn));
// This code is contributed by suresh07.
</script>
Producción
21
Nota:
Para realizar más tipos de operaciones, solo es necesario modificar la tabla de casos de interruptores. Esta implementación solo funciona para operandos de un solo dígito. Los operandos de varios dígitos se pueden implementar si se usa algún espacio similar a un carácter para separar los operandos y los operadores.
A continuación se muestra el programa extendido que permite que los operandos tengan varios dígitos.
C++
// C++ program to evaluate a prefix expression.
#include <bits/stdc++.h>
using namespace std;
double evaluatePrefix(string exprsn)
{
stack<double> Stack;
for (int j = exprsn.size() - 1; j >= 0; j--) {
// if jth character is the delimiter ( which is
// space in this case) then skip it
if (exprsn[j] == ' ')
continue;
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isdigit(exprsn[j])) {
// there may be more than
// one digits in a number
double num = 0, i = j;
while (j < exprsn.size() && isdigit(exprsn[j]))
j--;
j++;
// from [j, i] exprsn contains a number
for (int k = j; k <= i; k++)
num = num * 10 + double(exprsn[k] - '0');
Stack.push(num);
}
else {
// Operator encountered
// Pop two elements from Stack
double o1 = Stack.top();
Stack.pop();
double o2 = Stack.top();
Stack.pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn[j]) {
case '+':
Stack.push(o1 + o2);
break;
case '-':
Stack.push(o1 - o2);
break;
case '*':
Stack.push(o1 * o2);
break;
case '/':
Stack.push(o1 / o2);
break;
}
}
}
return Stack.top();
}
// Driver code
int main()
{
string exprsn = "+ 9 * 12 6";
cout << evaluatePrefix(exprsn) << endl;
return 0;
// this code is contributed by Mohd Shaad Khan
}
Java
// Java program to evaluate a prefix expression.
import java.util.*;
public class Main
{
static boolean isdigit(char ch)
{
if(ch >= 48 && ch <= 57)
{
return true;
}
return false;
}
static double evaluatePrefix(String exprsn)
{
Stack<Double> stack = new Stack<Double>();
for (int j = exprsn.length() - 1; j >= 0; j--) {
// if jth character is the delimiter ( which is
// space in this case) then skip it
if (exprsn.charAt(j) == ' ')
continue;
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isdigit(exprsn.charAt(j))) {
// there may be more than
// one digits in a number
double num = 0, i = j;
while (j < exprsn.length() && isdigit(exprsn.charAt(j)))
j--;
j++;
// from [j, i] exprsn contains a number
for (int k = j; k <= i; k++)
{
num = num * 10 + (double)(exprsn.charAt(k) - '0');
}
stack.push(num);
}
else {
// Operator encountered
// Pop two elements from Stack
double o1 = (double)stack.peek();
stack.pop();
double o2 = (double)stack.peek();
stack.pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn.charAt(j)) {
case '+':
stack.push(o1 + o2);
break;
case '-':
stack.push(o1 - o2);
break;
case '*':
stack.push(o1 * o2);
break;
case '/':
stack.push(o1 / o2);
break;
}
}
}
return stack.peek();
}
// Driver code
public static void main(String[] args) {
String exprsn = "+ 9 * 12 6";
System.out.print((int)evaluatePrefix(exprsn));
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program to evaluate a prefix expression.
def isdigit(ch):
if(ord(ch) >= 48 and ord(ch) <= 57):
return True
return False
def evaluatePrefix(exprsn):
Stack = []
for j in range(len(exprsn) - 1, -1, -1):
# if jth character is the delimiter ( which is
# space in this case) then skip it
if (exprsn[j] == ' '):
continue
# Push operand to Stack
# To convert exprsn[j] to digit subtract
# '0' from exprsn[j].
if (isdigit(exprsn[j])):
# there may be more than
# one digits in a number
num, i = 0, j
while (j < len(exprsn) and isdigit(exprsn[j])):
j-=1
j+=1
# from [j, i] exprsn contains a number
for k in range(j, i + 1, 1):
num = num * 10 + (ord(exprsn[k]) - ord('0'))
Stack.append(num)
else:
# Operator encountered
# Pop two elements from Stack
o1 = Stack[-1]
Stack.pop()
o2 = Stack[-1]
Stack.pop()
# Use switch case to operate on o1
# and o2 and perform o1 O o2.
if exprsn[j] == '+':
Stack.append(o1 + o2 + 12)
elif exprsn[j] == '-':
Stack.append(o1 - o2)
elif exprsn[j] == '*':
Stack.append(o1 * o2 * 5 )
elif exprsn[j] == '/':
Stack.append(o1 / o2)
return Stack[-1]
exprsn = "+ 9 * 12 6"
print(evaluatePrefix(exprsn))
# This code is contributed by divyesh072019.
C#
// C# program to evaluate a prefix expression.
using System;
using System.Collections;
class GFG {
static bool isdigit(char ch)
{
if(ch >= 48 && ch <= 57)
{
return true;
}
return false;
}
static double evaluatePrefix(string exprsn)
{
Stack stack = new Stack();
for (int j = exprsn.Length - 1; j >= 0; j--) {
// if jth character is the delimiter ( which is
// space in this case) then skip it
if (exprsn[j] == ' ')
continue;
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isdigit(exprsn[j])) {
// there may be more than
// one digits in a number
double num = 0, i = j;
while (j < exprsn.Length && isdigit(exprsn[j]))
j--;
j++;
// from [j, i] exprsn contains a number
for (int k = j; k <= i; k++)
{
num = num * 10 + (double)(exprsn[k] - '0');
}
stack.Push(num);
}
else {
// Operator encountered
// Pop two elements from Stack
double o1 = (double)stack.Peek();
stack.Pop();
double o2 = (double)stack.Peek();
stack.Pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn[j]) {
case '+':
stack.Push(o1 + o2);
break;
case '-':
stack.Push(o1 - o2);
break;
case '*':
stack.Push(o1 * o2);
break;
case '/':
stack.Push(o1 / o2);
break;
}
}
}
return (double)stack.Peek();
}
static void Main() {
string exprsn = "+ 9 * 12 6";
Console.Write(evaluatePrefix(exprsn));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to evaluate a prefix expression.
function isdigit(ch)
{
if(ch.charCodeAt() >= 48 && ch.charCodeAt() <= 57)
{
return true;
}
return false;
}
function evaluatePrefix(exprsn)
{
let Stack = [];
for (let j = exprsn.length - 1; j >= 0; j--) {
// if jth character is the delimiter ( which is
// space in this case) then skip it
if (exprsn[j] == ' ')
continue;
// Push operand to Stack
// To convert exprsn[j] to digit subtract
// '0' from exprsn[j].
if (isdigit(exprsn[j])) {
// there may be more than
// one digits in a number
let num = 0, i = j;
while (j < exprsn.length && isdigit(exprsn[j]))
j--;
j++;
// from [j, i] exprsn contains a number
for (let k = j; k <= i; k++)
num = num * 10 + (exprsn[k].charCodeAt() - '0'.charCodeAt());
Stack.push(num);
}
else {
// Operator encountered
// Pop two elements from Stack
let o1 = Stack[Stack.length - 1];
Stack.pop();
let o2 = Stack[Stack.length - 1];
Stack.pop();
// Use switch case to operate on o1
// and o2 and perform o1 O o2.
switch (exprsn[j]) {
case '+':
Stack.push(o1 + o2);
break;
case '-':
Stack.push(o1 - o2);
break;
case '*':
Stack.push(o1 * o2);
break;
case '/':
Stack.push(o1 / o2);
break;
}
}
}
return Stack[Stack.length - 1];
}
let exprsn = "+ 9 * 12 6";
document.write(evaluatePrefix(exprsn));
// This code is contributed by rameshtravel07.
</script>
Producción
81
Complejidad temporal: O(n)
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA