2 releases
0.1.1 | Dec 21, 2022 |
---|---|
0.1.0 | Dec 20, 2022 |
#1821 in Algorithms
18KB
261 lines
fixit
Converts infix tokens to postfix tokens, otherwise known as https://en.wikipedia.org/wiki/Reverse_Polish_notation.
This library does not do parsing or execution of expressions, but only filters/reorders tokens to allow stack-based execution. The (possibly less efficient) alternative to stack-based execution usually involves walking an expression tree.
Example
use fixit::{BinaryOperator, InfixToken, convert};
// Define your own operand: it could be anything.
type MyOperand = f32;
// Define your own operator.
enum MyBinaryOp {
Add,
Sub,
Mul,
Div,
}
// Assign a precedence to each operator
impl BinaryOperator for MyBinaryOp {
fn precedence(&self) -> u8 {
match self {
MyBinaryOp::Add => 1,
MyBinaryOp::Sub => 1,
MyBinaryOp::Mul => 2,
MyBinaryOp::Div => 2,
}
}
}
type MyInfixToken = InfixToken<MyOperand, MyBinaryOp>;
// The incoming `expr` tokens could have been parsed from a string via a crate like `nom` or `pest`.
// Parsing an expression like "a + b * c + d" should give:
// vec![
// InfixToken::Operand("a"), InfixToken::BinaryOp(MyBinaryOp::Add), InfixToken::Operand("b"),
// InfixToken::BinaryOp(MyBinaryOp::Mul),
// InfixToken::Operand("c"), InfixToken::BinaryOp(MyBinaryOp::Add), InfixToken::Operand("d")
// ]
fn example(expr: Vec<MyInfixToken>) {
// Convert to postfix. The result will contain:
// vec![
// PostfixToken::Operand("a"),
// PostfixToken::Operand("b"),
// PostfixToken::Operand("c"),
// PostfixToken::BinaryOp(MyBinaryOp::Mul),
// PostfixToken::BinaryOp(MyBinaryOp::Add),
// PostfixToken::Operand("d"),
// PostfixToken::BinaryOp(MyBinaryOp::Add)
// ]
let postfix_tokens = convert(expr);
// We don't aim to provide a full explanation of postfix expressions here, but
// the expression can now be evaluated by iterating over postfix tokens,
// pushing and popping values off a stack.
}
License: MIT OR Apache-2.0