¿Qué es la notación infija?
Una notación infija es una notación en la que una expresión se escribe en un formato habitual o normal. Es una notación en la que los operadores se encuentran entre los operandos. Los ejemplos de notación infija son A+B, A*B, A/B, etc.
Como podemos ver en los ejemplos anteriores, todos los operadores existen entre los operandos, por lo que son notaciones infijas. Por tanto, la sintaxis de la notación infija se puede escribir como:
Analizando expresiones infijas
Para analizar cualquier expresión, debemos ocuparnos de dos cosas, es decir, Prioridad del operador y asociatividad . Precedencia de operadores significa la precedencia de cualquier operador sobre otro operador. Por ejemplo:
A + B * C → A + (B * C)
Como el operador de multiplicación tiene mayor prioridad sobre el operador de suma, la expresión B * C se evaluará primero. El resultado de la multiplicación de B * C se suma a la A.
Orden de precedencia
| Operadores | Símbolos |
|---|---|
| Paréntesis | { }, ( ), [ ] |
| Notación exponencial | ^ |
| Multiplicación y división | *, / |
| Adición y sustracción | +, - |
Asociatividad significa cuando existen operadores con la misma precedencia en la expresión. Por ejemplo, en la expresión, es decir, A + B - C, los operadores '+' y '-' tienen la misma precedencia, por lo que se evalúan con la ayuda de la asociatividad. Dado que tanto '+' como '-' son asociativos por la izquierda, se evaluarían como (A + B) - C.
Orden de asociatividad
| Operadores | asociatividad |
|---|---|
| ^ | De derecha a izquierda |
| *, / | De izquierda a derecha |
| +, - | De izquierda a derecha |
Entendamos la asociatividad a través de un ejemplo.
1 + 2*3 + 30/5
Dado que en la expresión anterior, * y / tienen la misma precedencia, aplicaremos la regla de asociatividad. Como podemos observar en la tabla anterior, los operadores * y / tienen asociatividad de izquierda a derecha, por lo que escanearemos desde el operador más a la izquierda. El operador que llegue primero será evaluado primero. El operador * aparece antes del operador / y la multiplicación se haría primero.
1+ (2*3) + (30/5)
1+6+6 = 13
¿Qué es la notación de prefijo?
Una notación de prefijo es otra forma de expresión, pero no requiere otra información como precedencia y asociatividad, mientras que una notación de infijo requiere información de precedencia y asociatividad. También se le conoce como notación polaca . En notación de prefijo, un operador va antes de los operandos. La sintaxis de la notación de prefijo se proporciona a continuación:
Por ejemplo, si la expresión infija es 5 + 1, entonces la expresión de prefijo correspondiente a esta expresión infija es +51.
Si la expresión infija es:
a*b+c
conjunto de hash java
↓
*ab+c
↓
+*abc (Expresión de prefijo)
Considere otro ejemplo:
A+B*C
Primer escaneo: En la expresión anterior, el operador de multiplicación tiene mayor prioridad que el operador de suma; la notación de prefijo de B*C sería (*BC).
A + *BC
Segundo escaneo: En el segundo escaneo, el prefijo sería:
+A *BC
En la expresión anterior, utilizamos dos escaneos para convertir una expresión de infijo en prefijo. Si la expresión es compleja, entonces requerimos una mayor cantidad de escaneos. Necesitamos utilizar ese método que requiere solo un escaneo y proporciona el resultado deseado. Si logramos el resultado deseado mediante un escaneo, entonces el algoritmo sería eficiente. Esto sólo es posible utilizando una pila.
Conversión de infijo a prefijo usando Stack
K + L - M * N + (O^P) * W/U/V * T + Q
Si estamos convirtiendo la expresión de infijo a prefijo, primero debemos invertir la expresión.
.siguiente java
La expresión inversa sería:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Para obtener la expresión de prefijo, hemos creado una tabla que consta de tres columnas, es decir, expresión de entrada, pila y expresión de prefijo. Cuando encontramos algún símbolo, simplemente lo agregamos a la expresión del prefijo. Si encontramos al operador, lo introduciremos en la pila.
| Expresión de entrada | Pila | Expresión de prefijo |
|---|---|---|
| q | q | |
| + | + | q |
| t | + | cuarto de galón |
| * | +* | cuarto de galón |
| EN | +* | qtv |
| / | +*/ | qtv |
| EN | +*/ | QTVU |
| / | +*// | QTVU |
| EN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| PAG | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| oh | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| norte | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| METRO | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| l | ++- | QTVUWPO^*//*NM*L |
| + | ++-+ | QTVUWPO^*//*NM*L |
| k | ++-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK++-++ |
La expresión anterior, es decir, QTVUWPO^*//*NM*LK++-++, no es una expresión final. Necesitamos invertir esta expresión para obtener la expresión del prefijo.
Reglas para la conversión de expresión de infijo a prefijo:
- Primero, invierta la expresión infija dada en el problema.
- Escanee la expresión de izquierda a derecha.
- Siempre que lleguen los operandos, imprímalos.
- Si llega el operador y descubre que la pila está vacía, simplemente empújelo hacia la pila.
- Si el operador entrante tiene mayor prioridad que la PARTE SUPERIOR de la pila, empújelo hacia la pila.
- Si el operador entrante tiene la misma prioridad que la parte SUPERIOR de la pila, empuje al operador entrante hacia la pila.
- Si el operador entrante tiene menor prioridad que la PARTE SUPERIOR de la pila, extraiga e imprima la parte superior de la pila. Pruebe nuevamente el operador entrante contra la parte superior de la pila y saque el operador de la pila hasta que encuentre el operador de menor precedencia o de misma precedencia.
- Si el operador entrante tiene la misma precedencia que la parte superior de la pila y el operador entrante es ^, entonces saque la parte superior de la pila hasta que la condición sea verdadera. Si la condición no es verdadera, presione el operador ^.
- Cuando lleguemos al final de la expresión, extraiga e imprima todos los operadores de la parte superior de la pila.
- Si el operador es ')', empújelo hacia la pila.
- Si el operador es '(', saque todos los operadores de la pila hasta que encuentre ) corchete de apertura en la pila.
- Si la parte superior de la pila es ')', empuje al operador sobre la pila.
- Al final, invierta la salida.
Pseudocódigo de conversión de infijo a prefijo
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>