Expresión infija : La expresión de la forma a op b. Cuando un operador está entre cada par de operandos.
Postfix expression : La expresión de la forma ab op. Cuando se sigue un operador para cada par de operandos.
La notación postfija, también conocida como notación polaca inversa, es una sintaxis para expresiones matemáticas en las que el operador matemático siempre se coloca después de los operandos. Aunque los ordenadores evalúan fácil y eficientemente las expresiones de posfijo, pueden ser difíciles de leer para los humanos. Las expresiones complejas que utilizan la notación de infijo entre paréntesis estándar suelen ser más legibles que las expresiones de sufijo correspondientes. En consecuencia, a veces nos gustaría permitir que los usuarios finales trabajen con notación infija y luego la conviertan a notación postfija para el procesamiento informático. A veces, además, las expresiones se almacenan o generan en sufijo, y nos gustaría convertirlas a infijo con el fin de leer y editar
Ejemplos:
Input : abc++ Output : (a + (b + c)) Input : ab*c+ Output : ((a*b)+c)
Ya hemos hablado de Infix a Postfix . A continuación se muestra el algoritmo para Postfix a Infix.
Algoritmo
1.Mientras queden símbolos de entrada
… 1.1 Lea el siguiente símbolo de la entrada.
2.Si el símbolo es un operando
… 2.1 Póngalo en la pila.
3.De lo contrario,
…3.1 el símbolo es un operador.
…3.2 Extraiga los 2 valores superiores de la pila.
…3.3 Poner el operador, con los valores como argumentos y formar una string.
…3.4 Vuelva a colocar la string resultante en la pila.
4. Si solo hay un valor en la pila
… 4.1 Ese valor en la pila es la string infija deseada.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find infix for
// a given postfix.
#include <bits/stdc++.h>
using namespace std;
bool isOperand(char x)
{
return (x >= 'a' && x <= 'z') ||
(x >= 'A' && x <= 'Z');
}
// Get Infix for a given postfix
// expression
string getInfix(string exp)
{
stack<string> s;
for (int i=0; exp[i]!='\0'; i++)
{
// Push operands
if (isOperand(exp[i]))
{
string op(1, exp[i]);
s.push(op);
}
// We assume that input is
// a valid postfix and expect
// an operator.
else
{
string op1 = s.top();
s.pop();
string op2 = s.top();
s.pop();
s.push("(" + op2 + exp[i] +
op1 + ")");
}
}
// There must be a single element
// in stack now which is the required
// infix.
return s.top();
}
// Driver code
int main()
{
string exp = "ab*c+";
cout << getInfix(exp);
return 0;
}
Java
// Java program to find infix for
// a given postfix.
import java.util.*;
class GFG
{
static boolean isOperand(char x)
{
return (x >= 'a' && x <= 'z') ||
(x >= 'A' && x <= 'Z');
}
// Get Infix for a given postfix
// expression
static String getInfix(String exp)
{
Stack<String> s = new Stack<String>();
for (int i = 0; i < exp.length(); i++)
{
// Push operands
if (isOperand(exp.charAt(i)))
{
s.push(exp.charAt(i) + "");
}
// We assume that input is
// a valid postfix and expect
// an operator.
else
{
String op1 = s.peek();
s.pop();
String op2 = s.peek();
s.pop();
s.push("(" + op2 + exp.charAt(i) +
op1 + ")");
}
}
// There must be a single element
// in stack now which is the required
// infix.
return s.peek();
}
// Driver code
public static void main(String args[])
{
String exp = "ab*c+";
System.out.println( getInfix(exp));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find infix for
# a given postfix.
def isOperand(x):
return ((x >= 'a' and x <= 'z') or
(x >= 'A' and x <= 'Z'))
# Get Infix for a given postfix
# expression
def getInfix(exp) :
s = []
for i in exp:
# Push operands
if (isOperand(i)) :
s.insert(0, i)
# We assume that input is a
# valid postfix and expect
# an operator.
else:
op1 = s[0]
s.pop(0)
op2 = s[0]
s.pop(0)
s.insert(0, "(" + op2 + i +
op1 + ")")
# There must be a single element in
# stack now which is the required
# infix.
return s[0]
# Driver Code
if __name__ == '__main__':
exp = "ab*c+"
print(getInfix(exp.strip()))
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to find infix for
// a given postfix.
using System;
using System.Collections;
class GFG
{
static Boolean isOperand(char x)
{
return (x >= 'a' && x <= 'z') ||
(x >= 'A' && x <= 'Z');
}
// Get Infix for a given postfix
// expression
static String getInfix(String exp)
{
Stack s = new Stack();
for (int i = 0; i < exp.Length; i++)
{
// Push operands
if (isOperand(exp[i]))
{
s.Push(exp[i] + "");
}
// We assume that input is
// a valid postfix and expect
// an operator.
else
{
String op1 = (String) s.Peek();
s.Pop();
String op2 = (String) s.Peek();
s.Pop();
s.Push("(" + op2 + exp[i] +
op1 + ")");
}
}
// There must be a single element
// in stack now which is the required
// infix.
return (String)s.Peek();
}
// Driver code
public static void Main(String []args)
{
String exp = "ab*c+";
Console.WriteLine( getInfix(exp));
}
}
// This code is contributed by Arnab Kundu
PHP
<?php
class Stack {
protected $stack;
protected $limit;
function CreateStack($limit){
$this->stack = array();
$this->limit = $limit;
}
function push($item) {
// trap for stack overflow
if (count($this->stack) < $this->limit) {
// prepend item to the start of the array
array_unshift($this->stack, $item);
} else {
throw new RunTimeException('Stack is full!');
}
}
function pop() {
if ($this->isEmpty()) {
// trap for stack underflow
throw new RunTimeException('Stack is empty!');
} else {
// pop item from the start of the array
return array_shift($this->stack);
}
}
function top() {
return current($this->stack);
}
function isEmpty() {
return empty($this->stack);
}
function Prec($ch)
{
switch ($ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
function isOperand($ch)
{
return ($ch >= 'a' && $ch <= 'z') || ($ch >= 'A' && $ch <= 'Z');
}
function isOperator($x) {
switch ($x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
public function getInfix($exp)
{
$this->CreateStack(sizeof($exp));
for ($i=0; $exp[$i]!= null; $i++)
{
// Push operands
if ($this->isOperand($exp[$i]))
{
$op = $exp[$i];
$this->push($op);
}
// We assume that input is
// a valid postfix and expect
// an operator.
else
{
$op1 = $this->top(); $this->pop();
$op2 = $this->top(); $this->pop();
$this->push("(". $op2 . $exp[$i] . $op1 . ")");
//$this->push($temp);
}
}
// There must be a single element
// in stack now which is the required
// infix.
return $this->top();
}
}
$myExample = new Stack();
echo $input = "ab*c+";
$exp = str_split($input,sizeof($input));
echo '<br>'.$data = $myExample->getInfix($exp);
?>
Javascript
<script>
// JavaScript program to find infix for
// a given postfix.
function isOperand(x)
{
return (x >= 'a' && x <= 'z') ||
(x >= 'A' && x <= 'Z');
}
// Get Infix for a given postfix
// expression
function getInfix(exp)
{
let s = [];
for (let i = 0; i < exp.length; i++)
{
// Push operands
if (isOperand(exp[i]))
{
s.push(exp[i] + "");
}
// We assume that input is
// a valid postfix and expect
// an operator.
else
{
let op1 = s.pop();
let op2 = s.pop();
s.pop();
s.push("(" + op2 + exp[i] +
op1 + ")");
}
}
// There must be a single element
// in stack now which is the required
// infix.
return s[s.length-1];
}
// Driver code
let exp = "ab*c+";
document.write( getInfix(exp));
// This code is contributed by avanitrachhadiya2155
</script>
((a*b)+c)
Complejidad de tiempo: O(N) donde N es la longitud de la string
Espacio auxiliar: O(N) donde N es el tamaño de la pila.
Publicación traducida automáticamente
Artículo escrito por PUSHPENDER SINGH y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA