O que é notação infixa?
Uma notação infixa é uma notação na qual uma expressão é escrita em um formato usual ou normal. É uma notação em que os operadores ficam entre os operandos. Os exemplos de notação infixa são A+B, A*B, A/B, etc.
Como podemos ver nos exemplos acima, todos os operadores existem entre os operandos, portanto são notações infixas. Portanto, a sintaxe da notação infixa pode ser escrita como:
Analisando expressões Infix
Para analisar qualquer expressão, precisamos cuidar de duas coisas, ou seja, Operador precedente e Associatividade . Precedência do operador significa a precedência de qualquer operador sobre outro operador. Por exemplo:
A + B * C → A + (B * C)
lista de strings java
Como o operador de multiplicação tem uma precedência maior sobre o operador de adição, a expressão B * C será avaliada primeiro. O resultado da multiplicação de B * C é adicionado ao A.
Ordem de precedência
| Operadores | Símbolos |
|---|---|
| Parêntese | { }, ( ), [ ] |
| Notação exponêncial | ^ |
| Multiplicação e divisão | *, / |
| Adição e subtração | +, - |
Associatividade significa quando existem operadores com a mesma precedência na expressão. Por exemplo, na expressão, ou seja, A + B - C, os operadores '+' e '-' têm a mesma precedência, portanto são avaliados com a ajuda da associatividade. Como '+' e '-' são associativos à esquerda, eles seriam avaliados como (A + B) - C.
Ordem de associatividade
| Operadores | Associatividade |
|---|---|
| ^ | Direita para esquerda |
| *, / | Da esquerda para direita |
| +, - | Da esquerda para direita |
Vamos entender a associatividade através de um exemplo.
1 + 2*3 + 30/5
Como na expressão acima, * e / têm a mesma precedência, aplicaremos a regra de associatividade. Como podemos observar na tabela acima que os operadores * e / têm associatividade da esquerda para a direita, portanto faremos a varredura a partir do operador mais à esquerda. O operador que vier primeiro será avaliado primeiro. O operador * aparece antes do operador / e a multiplicação seria feita primeiro.
1+ (2*3) + (30/5)
1+6+6 = 13
O que é notação de prefixo?
Uma notação de prefixo é outra forma de expressão, mas não requer outras informações, como precedência e associatividade, enquanto uma notação infixa requer informações de precedência e associatividade. Também é conhecido como notação polonesa . Na notação de prefixo, um operador vem antes dos operandos. A sintaxe da notação de prefixo é fornecida abaixo:
Por exemplo, se a expressão infixa for 5+1, então a expressão prefixa correspondente a esta expressão infixa será +51.
Se a expressão infixa for:
a*b+c
↓
*ab+c
↓
+*abc (expressão de prefixo)
Considere outro exemplo:
A + B * C
Primeira verificação: Na expressão acima, o operador de multiplicação tem precedência maior que o operador de adição; a notação de prefixo de B*C seria (*BC).
A + *BC
Segunda varredura: Na segunda varredura, o prefixo seria:
+A *BC
Na expressão acima, usamos duas varreduras para converter expressão de infixo em prefixo. Se a expressão for complexa, será necessário um número maior de varreduras. Precisamos usar aquele método que requer apenas uma varredura e fornece o resultado desejado. Se alcançarmos a saída desejada por meio de uma varredura, o algoritmo será eficiente. Isso só é possível usando uma pilha.
Conversão de Infix em Prefix usando Stack
K + L - M * N + (O^P) * W/U/V * T + Q
Se estivermos convertendo a expressão de infixo em prefixo, precisamos primeiro reverter a expressão.
A expressão reversa seria:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Para obter a expressão de prefixo, criamos uma tabela que consiste em três colunas, ou seja, expressão de entrada, pilha e expressão de prefixo. Quando encontramos qualquer símbolo, simplesmente o adicionamos à expressão do prefixo. Se encontrarmos o operador, iremos colocá-lo na pilha.
| Expressão de entrada | Pilha | Expressão de prefixo |
|---|---|---|
| P | P | |
| + | + | P |
| T | + | QT |
| * | +* | QT |
| EM | +* | TVQ |
| / | +*/ | TVQ |
| EM | +*/ | QTVU |
| / | +*// | QTVU |
| EM | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| M | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| eu | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
A expressão acima, ou seja, QTVUWPO^*//*NM*LK+-++, não é uma expressão final. Precisamos reverter esta expressão para obter a expressão do prefixo.
Regras para a conversão de expressão infixa em prefixo:
- Primeiro, inverta a expressão infixa dada no problema.
- Digitalize a expressão da esquerda para a direita.
- Sempre que os operandos chegarem, imprima-os.
- Se o operador chegar e a pilha estiver vazia, simplesmente empurre o operador para dentro da pilha.
- Se o operador de entrada tiver precedência maior que o TOPO da pilha, coloque o operador de entrada na pilha.
- Se o operador de entrada tiver a mesma precedência com um TOPO da pilha, coloque o operador de entrada na pilha.
- Se o operador de entrada tiver precedência menor que o TOPO da pilha, abra e imprima o topo da pilha. Teste o operador de entrada no topo da pilha novamente e retire o operador da pilha até encontrar o operador de precedência inferior ou da mesma precedência.
- Se o operador de entrada tiver a mesma precedência com o topo da pilha e o operador de entrada for ^, então coloque o topo da pilha até que a condição seja verdadeira. Se a condição não for verdadeira, pressione o operador ^.
- Quando chegarmos ao final da expressão, pop e imprima todos os operadores do topo da pilha.
- Se o operador for ')', coloque-o na pilha.
- Se o operador for '(', retire todos os operadores da pilha até encontrar) colchete de abertura na pilha.
- Se o topo da pilha for ')', coloque o operador na pilha.
- No final, inverta a saída.
Pseudocódigo de conversão de infixo em prefixo
calculando a posse no excel
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))>