Antes de entender a conversão da notação infixa para pós-fixada, devemos saber sobre as notações infixas e pós-fixadas separadamente.

Um infixo e um postfix são as expressões. Uma expressão consiste em constantes, variáveis ​​e símbolos. Os símbolos podem ser operadores ou parênteses. Todos esses componentes devem ser organizados de acordo com um conjunto de regras para que todas essas expressões possam ser avaliadas usando o conjunto de regras.

Exemplos de expressões são:

5 + 6

A-B

(P * 5)

Todas as expressões acima possuem uma estrutura comum, ou seja, temos um operador entre os dois operandos. Um Operando é um objeto ou valor no qual a operação deve ser executada. Nas expressões acima, 5, 6 são os operandos enquanto '+', '-' e '*' são os operadores.

O que é notação infixa?

Quando o operador é escrito entre os operandos, ele é conhecido como notação infixa . O operando não precisa ser sempre uma constante ou uma variável; também pode ser uma expressão em si.

Por exemplo,

tipos de dados SQL

(p + q) * (r + s)

Na expressão acima, ambas as expressões do operador de multiplicação são os operandos, ou seja, (p + q) , e (r + s) são os operandos.

Na expressão acima, existem três operadores. Os operandos para o primeiro operador positivo são p e q, os operandos para o segundo operador positivo são r e s. Ao realizar o operações na expressão, precisamos seguir algum conjunto de regras para avaliar o resultado. No expressão acima, a operação de adição seria realizada nas duas expressões, ou seja, p+q e r+s, e então a operação de multiplicação seria realizada.

A sintaxe da notação infixa é fornecida abaixo:

Se houver apenas um operador na expressão, não é necessária a aplicação de nenhuma regra. Por exemplo, 5 + 2; nesta expressão, a operação de adição pode ser realizada entre os dois operandos (5 e 2), e o resultado da operação seria 7.

Se houver vários operadores na expressão, alguma regra deverá ser seguida para avaliar a expressão.

Se a expressão for:

4+6*2

Se o operador mais for avaliado primeiro, a expressão ficaria assim:

10 * 2 = 20

Se o operador de multiplicação for avaliado primeiro, a expressão ficaria assim:

4 + 12 = 16

O problema acima pode ser resolvido seguindo as regras de precedência de operadores. Na expressão algébrica, a ordem de precedência dos operadores é dada na tabela abaixo:

A primeira preferência é dada aos parênteses; então a próxima preferência é dada aos expoentes. No caso de operadores de múltiplos expoentes, a operação será aplicada da direita para a esquerda.

Por exemplo:

2 ^ 2 ^ 3 = 2 ^ 8

= 256

Após a avaliação dos operadores de expoente, multiplicação e divisão. Se ambos os operadores estiverem presentes na expressão, a operação será aplicada da esquerda para a direita.

A próxima preferência é dada à adição e subtração. Se ambos os operadores estiverem disponíveis na expressão, vamos da esquerda para a direita.

Os operadores que têm a mesma precedência denominados como associatividade do operador . Se formos da esquerda para a direita, isso é conhecido como associativo à esquerda. Se formos da direita para a esquerda, isso é conhecido como associativo à direita.

Problema com notação infixa

Para avaliar a expressão infixa, devemos saber sobre o operador precedente regras, e se os operadores tiverem a mesma precedência, então devemos seguir o associatividade regras. O uso de parênteses é muito importante na notação infixa para controlar a ordem em que a operação será executada. Parênteses melhora a legibilidade da expressão. Uma expressão infixa é a forma mais comum de escrever expressões, mas não é fácil analisar e avaliar a expressão infixa sem ambiguidade. Assim, matemáticos e lógicos estudaram este problema e descobriram duas outras formas de escrever expressões que são prefixo e pós-fixo. Ambas as expressões não requerem parênteses e podem ser analisadas sem ambiguidade. Não requer precedência de operador e regras de associatividade.

quanto é 10 de 1 milhão

Expressão Postfix

A expressão pós-fixada é uma expressão na qual o operador é escrito após os operandos. Por exemplo, a expressão pós-fixada de notação infixa (2+3) pode ser escrita como 23+.

Alguns pontos-chave em relação à expressão postfix são:

• Na expressão postfix, as operações são executadas na ordem em que foram escritas, da esquerda para a direita.
• Não requer nenhum parêntese.
• Não precisamos aplicar regras de precedência de operadores e regras de associatividade.

Algoritmo para avaliar a expressão pós-fixada

• Digitalize a expressão da esquerda para a direita até encontrar qualquer operador.
• Execute a operação
• Substitua a expressão pelo seu valor calculado.
• Repita as etapas de 1 a 3 até que não existam mais operadores.

Vamos entender o algoritmo acima por meio de um exemplo.

Expressão infixa: 2 + 3 * 4

Começaremos a escanear a partir da esquerda da expressão. O operador de multiplicação é um operador que aparece primeiro durante a varredura da esquerda para a direita. Agora, a expressão seria:

Expressão = 2 + 34*

= 2 + 12

Novamente, digitalizaremos da esquerda para a direita e a expressão seria:

Expressão = 2 12 +

= 14

Avaliação da expressão postfix usando pilha.

• Digitalize a expressão da esquerda para a direita.
• Se encontrarmos qualquer operando na expressão, colocamos o operando na pilha.
• Quando encontramos qualquer operador na expressão, retiramos os operandos correspondentes da pilha.
• Quando terminamos a digitalização da expressão, o valor final permanece na pilha.

Vamos entender a avaliação da expressão postfix usando pilha.

Exemplo 1: Expressão pós-fixada: 2 3 4 * +

O resultado da expressão acima é 14.

Exemplo 2: Expressão pós-fixada: 3 4 * 2 5 * +

O resultado da expressão acima é 22.

Algoritmo para avaliar expressão pós-fixada

'abc' está em números'

1. Ler um personagem
2. Se o caractere for um dígito, converta o caractere em int e coloque o inteiro na pilha.
3. Se o personagem for um operador,
   • Retire os elementos da pilha duas vezes obtendo dois operandos.
   • Execute a operação
   • Empurre o resultado para a pilha.

Conversão de infixo em postfix

Aqui, usaremos a estrutura de dados da pilha para a conversão da expressão infixa em expressão prefixada. Sempre que um operador é encontrado, colocamos o operador na pilha. Se encontrarmos um operando, acrescentamos o operando à expressão.

Regras para a conversão de expressão infixa em expressão pós-fixada

1. Imprima o operando conforme eles chegam.
2. Se a pilha estiver vazia ou contiver um parêntese esquerdo no topo, coloque o operador de entrada na pilha.
3. Se o símbolo recebido for '(', coloque-o na pilha.
4. Se o símbolo recebido for ')', abra a pilha e imprima os operadores até que o parêntese esquerdo seja encontrado.
5. Se o símbolo recebido tiver precedência maior que o topo da pilha, coloque-o na pilha.
6. Se o símbolo recebido tiver precedência menor que o topo da pilha, pop e imprima o topo da pilha. Em seguida, teste o operador recebido no novo topo da pilha.
7. Se o operador de entrada tiver a mesma precedência do topo da pilha, use as regras de associatividade. Se a associatividade for da esquerda para a direita, pop e imprima o topo da pilha e empurre o operador de entrada. Se a associatividade for da direita para a esquerda, pressione o operador de entrada.
8. No final da expressão, pop e imprima todos os operadores da pilha.

Vamos entender através de um exemplo.

Expressão infixa: K + L - M*N + (O^P) * W/U/V * T + Q

A expressão pós-fixada final da expressão infixa (K + L - M*N + (O^P) * W/U/V * T + Q) é KL+MN*-OP^W*U/V/T*+Q+ .