# 數學式的 Infix, Postfix, Postfix

## 中序轉換成後序 Infix To Postfix

#include <iostream>
#include <string>
#include <stack>
#include <cmath>
#include <cctype>

bool is_operant(char c){
    return isalnum(c);
}

bool is_operator(char c){
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^');
}

int op_priority(char c){
    int priority = 0;

    if(c == '+' || c == '-') priority = 1;
    else if(c == '*' || c == '/') priority = 2;
    else if(c == '^') priority = 3;

    return priority;
}

void peak_stack(std::stack<char> s){
    if(s.empty()) return;

    printf("+-----+\n");
    while(!s.empty()){
        printf("| %3c |\n" , s.top());
        printf("+-----+\n");
        s.pop();
    }
}

int main(){
    std::string input = "(a+b*c)/d-a";
    std::string result;
    std::stack<char> op;

    for(char c : input){
        if(c == '\0') break;
        std::cout << "c = \'" << c << "\'" << std::endl;
        if(is_operator(c) || c == '(' || c == ')'){
            // push into stack and check braclet
            std::cout << "> is operant\n";
            if(op.empty() || op_priority(op.top()) < op_priority(c)) op.push(c);
            else{
                std::cout << "> special case\n";
                while(!op.empty()){
                    if(op.top() != '(') result.push_back(op.top());
                    op.pop();
                }
                if(c != ')') op.push(c);
            }
        } else if(is_operant(c)){
            // push into result
            std::cout << "> is operator\n";
            result.push_back(c);
        }

        peak_stack(op);
        std::cout << "result= " << result << std::endl << std::endl;
    }

    while(!op.empty()){
        result.push_back(op.top());
        op.pop();
    }

    std::cout << result << std::endl;

    return 0;
}

## 中序轉換成前序 Infix to Prefix

#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <cmath>
#include <cctype>

bool is_operant(char c){
    return isalnum(c);
}

bool is_operator(char c){
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^');
}

int op_priority(char c){
    int priority = 0;

    if(c == '+' || c == '-') priority = 1;
    else if(c == '*' || c == '/') priority = 2;
    else if(c == '^') priority = 3;

    return priority;
}

template<class T>
void peak_stack(std::stack<T> s){
    if(s.empty()) return;
    std::cout.width(10);
    std::cout << "+----------+" << std::endl;
    while(!s.empty()){
        std::cout << std::left << "|" << std::setw(10) << s.top() << std::right << "|\n";
        std::cout << "+----------+" << std::endl;
        s.pop();
    }
}

int main(){
    std::string input = "(a+b*c)/d-a";
    std::stack<char> op;
    std::stack<std::string> result;

    for(char c : input){
        if(c == '\0') break;
        std::cout << "\nc = \'" << c << "\'" << std::endl;
        if(is_operator(c) || c == '(' || c == ')'){
            std::cout << "> is operator\n";
            if(op.empty() || op_priority(op.top()) < op_priority(c)) op.push(c);
            else{
                std::cout << "> special case\n";
                while(!op.empty()){
                    if(op.top() == '('){
                        op.pop();
                        continue;
                    }
                    std::string r1 = result.top();
                    result.pop();
                    std::string r2 = result.top();
                    result.pop();
                    std::string o ="";
                    if(op.top()!=')') o+=op.top();
                    o+=r1+r2;
                    result.push(o);
                    op.pop();
                }
                if(c!=')')op.push(c);
            }
        } else if(is_operant(c)){
            std::cout << "> is operant\n";
            std::string tmp = "";
            tmp.push_back(c);
            result.push(tmp);
        }
        
        std::cout << "op:" << std::endl;
        peak_stack(op);
        std::cout << "\nresult:" << std::endl;
        peak_stack(result);
    }
    while(!op.empty()){
        if(op.top() == '(') break;
        std::string r1 = result.top();
        result.pop();
        std::string r2 = result.top();
        result.pop();
        
        std::string o = "";
        if(op.top() != ')') o += op.top();
        o += r1 + r2;
        result.push(o);
        op.pop();
    }
    std::cout << "op:" << std::endl;
    peak_stack(op);
    std::cout << "\nresult:" << std::endl;
    peak_stack(result);

    std::cout <<"\nresult= "<< result.top() << std::endl;

    return 0;
}