Estrutura de dados - análise de expressão

A forma de escrever expressões aritméticas é conhecida como notation. Uma expressão aritmética pode ser escrita em três notações diferentes, mas equivalentes, ou seja, sem alterar a essência ou a saída de uma expressão. Essas notações são -

Notação Infix
Notação de prefixo (polonês)
Notação Postfix (polonês reverso)

Essas notações são nomeadas como usam o operador na expressão. Devemos aprender o mesmo aqui neste capítulo.

Notação Infix

Nós escrevemos expressão em infix notação, por exemplo, a - b + c, onde os operadores são usados in-entre operandos. É fácil para nós, humanos, ler, escrever e falar em notação infixa, mas o mesmo não funciona bem com dispositivos de computação. Um algoritmo para processar notação de infixação pode ser difícil e caro em termos de consumo de tempo e espaço.

Notação de prefixo

Nesta notação, o operador é prefixed para operandos, ou seja, o operador é escrito antes dos operandos. Por exemplo,+ab. Isso é equivalente à sua notação infixaa + b. A notação de prefixo também é conhecida comoPolish Notation.

Notação Postfix

Este estilo de notação é conhecido como Reversed Polish Notation. Neste estilo de notação, o operador épostfixed para os operandos, ou seja, o operador é escrito após os operandos. Por exemplo,ab+. Isso é equivalente à sua notação infixaa + b.

A tabela a seguir tenta mostrar brevemente a diferença em todas as três notações -

Sr. Não.	Notação Infix	Notação de prefixo	Notação Postfix
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	a ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - d	- ∗ + abcd	ab + c ∗ d -

Análise de expressões

Como discutimos, não é uma maneira muito eficiente de projetar um algoritmo ou programa para analisar notações infixas. Em vez disso, essas notações infixadas são primeiro convertidas em notações pós-fixadas ou prefixadas e depois calculadas.

Para analisar qualquer expressão aritmética, precisamos cuidar também da precedência do operador e da associatividade.

Precedência

Quando um operando está entre dois operadores diferentes, qual operador assumirá o operando primeiro, é decidido pela precedência de um operador sobre os outros. Por exemplo -

Como a operação de multiplicação tem precedência sobre a adição, b * c será avaliado primeiro. Uma tabela de precedência de operador é fornecida posteriormente.

Associatividade

A associatividade descreve a regra em que os operadores com a mesma precedência aparecem em uma expressão. Por exemplo, na expressão a + b - c, ambos + e - têm a mesma precedência, então qual parte da expressão será avaliada primeiro, é determinada pela associatividade desses operadores. Aqui, + e - são associativos à esquerda, então a expressão será avaliada como(a + b) − c.

A precedência e a associatividade determinam a ordem de avaliação de uma expressão. A seguir está uma tabela de precedência e associatividade do operador (da mais alta para a mais baixa) -

Sr. Não.	Operador	Precedência	Associatividade
1	Exponenciação ^	Altíssima	Associativo certo
2	Multiplicação (∗) e divisão (/)	Segundo mais alto	Esquerda Associativa
3	Adição (+) e subtração (-)	Mais baixo	Esquerda Associativa

A tabela acima mostra o comportamento padrão dos operadores. Em qualquer ponto do tempo na avaliação da expressão, a ordem pode ser alterada usando parênteses. Por exemplo -

No a + b*c, a parte da expressão b*cserão avaliados primeiro, com a multiplicação como precedência sobre a adição. Aqui usamos parênteses paraa + b para ser avaliado primeiro, como (a + b)*c.

Algoritmo de avaliação Postfix

Devemos agora olhar para o algoritmo sobre como avaliar a notação pós-fixada -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

Para ver a implementação na linguagem de programação C, clique aqui .