后缀表达式

后缀表达式 又称为 逆波兰表达式，适合计算机用来求表达式的值。计算后缀表达式的过程：

创建一个栈
从左到右扫描后缀表达式
如果遇到操作数，入栈
如果遇到运算符，弹出必要数量的操作数，执行运算，然后将结果入栈
表达式扫描完毕后，栈顶元素即为计算结果

这里的计算不用考虑优先级的事情，过程是显而易见的。

中缀表达式转后缀表达式

一般我们熟悉的表达式就是中缀表达式，如1+3*4-(5+6)。它适合人类计算，却不适合计算机。一般我们将中缀表达式转化成后缀表达式后求值。

创建一个用于存储操作符的栈和一个用于存储后缀表达式的结果列表
从左到右扫描中缀表达式
如果遇到操作数，直接加入结果列表
如果遇到左括号，入栈
如果遇到右括号，弹出栈中元素直到遇到左括号，并将弹出的操作符加入结果列表
如果遇到运算符，将其与栈顶运算符比较优先级：
1. 如果栈为空或栈顶为左括号，入栈
2. 如果优先级高于栈顶运算符，入栈
3. 如果优先级低于或等于栈顶运算符，弹出栈顶并加入结果列表，然后重复比较
扫描完成后，将栈中剩余的运算符弹出并加入结果列表

字节三面考察了这个知识点，然而我当时只记得有这个东西，完全忘记算法了。。。假设数字都是一位的，有加法，减法，括号的运算表达式字符串，计算它的值。

#[derive(PartialEq, Eq, Clone, Copy)]
enum Token {
    Number(i64),
    Operator(char),
    LP,
    RP,
}

impl Debug for Token {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Token::Number(n) => f.write_fmt(format_args!("{}", n)),
            Token::Operator(c) => f.write_char(*c),
            Token::LP => f.write_char('('),
            Token::RP => f.write_char(')'),
        }
    }
}

fn op_priority(op: char) -> usize {
    match op {
        '+' | '-' => 1,
        _ => unreachable!(),
    }
}

// !!! core
fn infix_to_postfix(tokens: Vec<Token>) -> Vec<Token> {
    let mut output_queue = Vec::new();
    let mut op_stack = Vec::new();
    for token in tokens {
        match token {
            Token::Number(_) => output_queue.push(token),
            Token::Operator(op) => {
                while let Some(top) = op_stack.last() {
                    match top {
                        Token::Operator(top_op) => {
                            if op_priority(*top_op) >= op_priority(op) {
                                output_queue.push(op_stack.pop().unwrap());
                            } else {
                                break;
                            }
                        }
                        Token::LP => {
                            break;
                        }
                        _ => unreachable!(),
                    }
                }
                op_stack.push(token);
            }
            Token::LP => op_stack.push(token),
            Token::RP => {
                while let Some(t) = op_stack.pop() {
                    if t == Token::LP {
                        break;
                    } else {
                        output_queue.push(t);
                    }
                }
            }
        }
    }
    while let Some(t) = op_stack.pop() {
        output_queue.push(t);
    }
    output_queue
}

// 这里针对的情况是 数字都是一位的
fn tokenize(s: &str) -> Vec<Token> {
    let mut tokens = Vec::new();
    for c in s.chars() {
        if c == '(' {
            tokens.push(Token::LP);
        } else if c == ')' {
            tokens.push(Token::RP);
        } else if c >= '0' && c <= '9' {
            tokens.push(Token::Number(c as i64 - '0' as i64));
        } else {
            tokens.push(Token::Operator(c));
        }
    }
    tokens
}

fn compute_postfix(postfix: Vec<Token>) -> i64 {
    let mut stack = Vec::new();
    for token in postfix {
        match token {
            Token::Number(n) => stack.push(n),
            Token::Operator(op) => {
                let rhs = stack.pop().unwrap();
                let lhs = stack.pop().unwrap();
                match op {
                    '+' => stack.push(lhs + rhs),
                    '-' => stack.push(lhs - rhs),
                    _ => unreachable!(),
                }
            }
            _ => unreachable!("paren in postfix"),
        }
    }
    assert_eq!(stack.len(), 1);
    return stack[0];
}

fn main() {
    let infix = "1-2+3+4-((5+6)-7)";
    let tokens = tokenize(infix);
    let postfix = infix_to_postfix(tokens);
    println!("postfix {:?}", postfix);
    let result = compute_postfix(postfix);
    println!("result = {}", result);
}