[ Conteúdo ] Demonstração da conversão de expressões infix para postfix usando Shunting yard algorithm
Aqui você irá ver uma simples demonstração do uso de um algoritmo muito importante, especialmente para compiladores, chamado Shunting yard algorithm.
Com Shunting yard algorithm nós podemos converter expressões infix para postfix. Se você não é familiarizado com estes termos, aqui esta um exemplo de uma expressão infix: 1 + 1. Aqui esta a mesma expressão em postfix: 1 1 +.
Disclaimer:
Isto não é uma implementação de um compilador. Não é um projeto completo também. Isto é apenas uma simples demonstração.
O que eu quero dizer com simples? Bem, eu não irei cobrir casos especiais, com exceção do parênteses. Não vou lidar com isto de maneira adequada, irei manipular strings para melhor visualização.
Os exemplos estão em Rust.
Definindo o core:
Primeiro eu defini um Enum para lidar com os tipos de operadores:
#[derive(Copy, Clone, Debug)]
pub enum Operator {
LeftParent,
Multi,
Add,
Sub,
Div,
}
Para utilizar o algoritmo, é necessário criar uma Stack. A minha implementação não cobre as funcionalidades padrões de que vemos no dia a dia, mas cobre parte delas. Além disso eu implementei métodos convenientes para manipular melhor a expressão.
Não se assuste com o tamanho do código:
#[derive(Debug)]
pub struct Stack {
stack: Vec<Operator>,
}
impl Stack {
pub fn new() -> Self {
Self {
stack: Vec::new()
}
}
pub fn operator_to_string(operator: &Operator) -> String {
match operator {
Operator::Add => String::from("+"),
Operator::Sub => String::from("-"),
Operator::Div => String::from("/"),
Operator::Multi => String::from("*"),
Operator::LeftParent => String::from("("),
}
}
pub fn top(&self) -> &Operator {
self.stack.last().expect("Return last item")
}
pub fn pop(&mut self) -> Operator {
self.stack.pop().expect("Remove last item")
}
pub fn push(&mut self, value: Operator) {
self.stack.push(value);
}
pub fn len(&self) -> usize {
self.stack.len()
}
pub fn is_empty(&self) -> bool {
self.stack.is_empty()
}
pub fn dry(&mut self) -> Vec<String> {
let mut remains: Vec<String> = Vec::new();
for _ in 0..self.len() {
match self.pop() {
Operator::Add => remains.push(String::from("+")),
Operator::Sub => remains.push(String::from("-")),
Operator::Div => remains.push(String::from("/")),
Operator::Multi => remains.push(String::from("*")),
_ => {
continue
}
}
}
remains
}
pub fn close_parenthesis(&mut self) -> Vec<String> {
let mut output: Vec<String> = Vec::new();
for _ in 0..self.len() {
match self.pop() {
Operator::Add => output.push(String::from("+")),
Operator::Sub => output.push(String::from("-")),
Operator::Div => output.push(String::from("/")),
Operator::Multi => output.push(String::from("*")),
Operator::LeftParent => break,
}
}
output
}
}
Com isso já temos o core. Agora vamos da uma olhado no que queremos alcançar através do algoritmo.
O algoritmo:
A ideia do algoritmo é muito simples. Temos duas estruturas, uma Stack e um Output. No Output colocamos os números. Na Stack colocamos os operadores "pendentes".
Output neste exemplos é um
Vetor.
Aqui esta alguns exemplos de expressão infix -> postfix respectivamente:
- 1 + 1 + 1 -> 1 1 + 1 +
- 1 - 1 + 1 -> 1 1 - 1 +
- 1 + 1 * 1 -> 1 1 1 * +
- 1 / 1 * 1 -> 1 1 / 1 *
- 1 + 1 * ( 2 + 2 ) -> 1 1 2 2 + * +
Para que realizar este processo? Há inúmeros motivos, e isto não é aplicado somente a expressões numéricas. Um bom exemplos são compiladores que utilizam deste algoritmo para converter expressões numéricas infix para postfix, pois como você bem sabe, computadores não entende humanos.
Agora que entendemos mais o nosso objetivo e temos o core implementado, vamos para o processo de conversão.
O processo:
Obtendo input
Primeiro eu criei uma função para obter o input do usuário atráves da CLI:
fn get_expression() -> Vec<String> {
let mut buffer = String::new();
io::stdin().read_line(&mut buffer).expect("To get expression");
let expressions: Vec<String> = buffer
.split_whitespace()
.map(|e| e.to_string())
.collect();
expressions
}
Isso vai obter o input, quebrar a String por whitespaces, então mapear novamente para String pois eu não queria um Vec<&str>.
Determinando o que entra e sai da stack:
Aqui o processo é bem simples. Primeiro eu vou receber uma Stack vazia, cujo foi criada na função main usando Stack::new().
Então irei criar o Output, então fazer um loop sobre o vector de input do usuário.
Cada caractere é avaliado individualmente e testado contra um determinado padrão no bloco match.
Para os operadores, eu chamo uma função que irá lidar com um detalhe importante do algoritmo que irei mencionar logo a seguir. Para o parenteses eu sempre foi inserir, pois ele é como uma "parede" e eu irei explicar o porquê logo.
fn eval_expressions(expressions: Vec<String>, stack: &mut Stack) {
let mut output: Vec<String> = Vec::new();
for e in expressions {
match e.as_str() {
"+" => output.append(&mut eval_operator(stack, Operator::Add)),
"-" => output.append(&mut eval_operator(stack, Operator::Sub)),
"/" => output.append(&mut eval_operator(stack, Operator::Div)),
"*" => output.append(&mut eval_operator(stack, Operator::Multi)),
"(" => stack.push(Operator::LeftParent),
")" => output.append(&mut stack.close_parenthesis()),
_ => {
output.push(e);
}
}
}
output.append(&mut stack.dry());
println!("{:?}", output);
println!("{:?}", stack);
}
Condição para o algoritmo funcionar:
Aqui temos que prestar bem atenção. Não podemos simplesmente inserir os operadores na Stack conforme nos encontramos com eles no loop.
Tenha em mente que: Antes de inserir o próximo precisamos fazer uma verificação de precedência. Se o próximo operador a ser inserido na stack tem uma precedência menor ou equivalente ao operador do top da Stack, então damos um pop na Stack, removendo o elemento do topo, então adicionamos o novo operador a Stack.
Para simplificar considere:
Stack: [+]
Próximo operador a ser inserido na Stack: +.
O operador + tem o mesmo valor de precedência, então removemos o valor da Stack com o método pop, adicionamos este valor removido ao Output, então adicionamos o Próximo operador na Stack.
Outro exemplo:
Stack: [+]
Próximo operador a ser inserido na Stack: -.
O operador de subtração tem o mesmo valor de precedência que o operador de soma, portanto removemos o elemento do topo usando o método pop, que atualmente é +, adicionamos ao Output então inserimos o - na Stack. No fim iremos ter uma Stack assim: [-].
O último exemplo:
Stack: [+, *]
Próximo operador a ser inserido na Stack: -.
aqui - é menor que * em termos de precedência, então fazemos o mesmo processo que acima. Damos um pop, isto remove o elemento do topo da Stack, então adicionamos ao Output, então verificamos novamente o teste para verificar se o próximo operador permite que eu insira o -. Neste caso chegamos ao +, e o processo repete.
Em termos de expressão, temos: 1 + 1 * 1 - 1 que em postfix seria: 1 1 1 * + -
Provavelmente você estranhou algo.
Se eu estiver inserindo um operador de maior precedência que o topo da Stack, eu não removo nada, eu apenas adiciona a Stack. Por isso que acima, ficou: 1 1 1 e não 1 1 + 1 * -
O código
fn precedence(operator: &Operator) -> u8 {
match operator {
Operator::Add | Operator::Sub => 0,
Operator::Multi | Operator::Div => 1,
Operator::LeftParent => 2,
}
}
fn eval_operator(stack: &mut Stack, incoming: Operator) -> Vec<String> {
let mut buffer: Vec<String> = Vec::new();
if stack.is_empty() {
stack.push(incoming);
return buffer
};
let stack_top = stack.top();
if let Operator::LeftParent = stack_top {
stack.push(incoming);
return buffer;
};
if should_pop_operator(stack_top, &incoming) {
let operator = stack.pop();
buffer.push(Stack::operator_to_string(&operator));
stack.push(incoming);
return buffer;
} else {
stack.push(incoming);
return buffer;
};
}
fn should_pop_operator(stack_top: &Operator, incoming: &Operator) -> bool {
precedence(incoming) <= precedence(stack_top)
}
Aqui definimos o valor das precedências com a função precedence. Então criamos uma função chamada should_pop_operator usado para remover o operador da Stack em casos onde o próximo operador a ser inserido, é equivalente ou menor ao operador no topo da pilha. Caso contrário apenas insere ele.
Parênteses
Vamos falar do caso especial, parentêses. Vocês sabem que parênteses altera a ordem da precedência, e por isso temos que lidar com este caso especial de maneira minuciosa.
Quando encontramos um ( nós sempre adicionamos ele a Stack. Ele é uma "parede" que separa o operadores anteriores aos que vêm a seguir. Na expressão: 1 + 1 + ( 2 + 2) a Stack ficaria mais ou menos assim: [+, (, +]. Um dos operadores de soma é removido da Stack pelo os motivos mencionados na seção anterior.
Como você pode ver, a Stack ficaria assim: [+, (, +] para a expressão acima. Se não tivesse este parênteses ai, ocorreria mais uma remoção do operador +.
Quando encontramos um ), vamos dando um pop na Stack até que encontre ( (removendo o parênteses também), assim você "fecha" o parênteses e remove ele na versão postfix.
Exemplo final:
Esta é uma tabela gerada por IA (pois não quero fazer trabalho repetitivo) para a expressão: 2 * 2 / 2 * ( 2 + 2 * 59 )
Token | Action | Output Queue | Operator Stack
------|-------------------------------|---------------------------|---------------
2 | Operand → output | [2] | []
* | Push | [2] | [*]
2 | Operand → output | [2, 2] | [*]
/ | Pop * → output, Push / | [2, 2, *] | [/]
2 | Operand → output | [2, 2, *, 2] | [/]
* | Pop / → output, Push * | [2, 2, *, 2, /] | [*]
( | Push | [2, 2, *, 2, /] | [*, (]
2 | Operand → output | [2, 2, *, 2, /, 2] | [*, (]
+ | Push | [2, 2, *, 2, /, 2] | [*, (, +]
2 | Operand → output | [2, 2, *, 2, /, 2, 2] | [*, (, +]
* | Push | [2, 2, *, 2, /, 2, 2] | [*, (, +, *]
59 | Operand → output | [2, 2, *, 2, /, 2, 2, 59] | [*, (, +, *]
) | Pop * and + → output, drop ( | [2, 2, *, 2, /, 2, 2, 59, *, +] | [*]
END | Pop * → output | [2, 2, *, 2, /, 2, 2, 59, *, +, *] | []
Fatos engraçados sobre o post:
- Estou criando o post mesmo sabendo que minha didática é horrível, então poucos entenderam, se houver alguém que entenda.
- Me custou 11 prompts para a IA me gerar a tabela acima
- Quando terminei meu projeto e rodei com a expressão acima, o Claude me disse que eu esta errado no inicio e terminou afirmando que eu estava correto.
Obrigado
Obrigado por ler até aqui!