HoshinoAya

use std::collections::VecDeque;

fn to_postfix(infix: &str) -> String {
    let preced = |op: char| match op {
        '(' | ')' => 1,
        '^' => 2,
        '*' | '/' => 3,
        '+' | '-' => 4,
        _ => unreachable!()
    };
    let op_left_assoc = |op: char| match op {
        '^' => false,
        _ => true
    };
    let mut stack: VecDeque<char> = VecDeque::new();
    let mut output = String::new();
    for x in infix.chars() {
        match x {
            ch if ch.is_digit(10) => output.push(ch),
            '+' | '-' | '*' | '/' | '^' => {
                while let Some(&op) = stack.back() {
                    if !(op != '(' && ((op_left_assoc(x) && preced(x) >= preced(op)) ||
                        (!op_left_assoc(x) && preced(x) > preced(op)))) {
                        break;
                    }

                    output.push(op);
                    stack.pop_back();
                }
                stack.push_back(x);
            }
            '(' => stack.push_back(x),
            ')' => {
                while let Some(op) = stack.pop_back() {
                    if op == '(' { break; }
                    output.push(op);
                }
            }
            _ => unreachable!()
        }
    }
    output.push_str(stack.iter().rev()
        .filter(|&&x| x != '(' && x != ')').collect::<String>().as_str());
    output
}

// Add your tests here.
// See https://doc.rust-lang.org/stable/rust-by-example/testing/unit_testing.html

#[cfg(test)]
mod tests {
    use itertools::Itertools;
    use super::to_postfix;
    
    fn do_test(actual: &str, expected: &str) {
        assert_eq!(actual, expected, "\nYour answer (left) is not the correct answer (right)")
    }

    #[test]
    fn fixed_tests() {
        do_test(&to_postfix("2+7*5"), "275*+");
        do_test(&to_postfix("3*3/(7+1)"), "33*71+/");
        do_test(&to_postfix("5+(6-2)*9+3^(7-1)"), "562-9*+371-^+");
        do_test(&to_postfix("(5-4-1)+9/5/2-7/1/7"), "54-1-95/2/+71/7/-");
        do_test(&to_postfix("1^2^3"), "123^^");
    }
}[]()