Shunting-yard with functions

ShuntingYard.cpp

//
//  main.cpp
//  Texnoman
//
//  Created by Ruslan Abdullaev on 11/23/18.
//  Copyright © 2018 Ruslan Abdullaev. All rights reserved.
//
//  Post: https://www.texnoman.uz/post/shuntingyard-algoritmi.html

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <cctype>
#include <sstream>
#include <stack>
#include <memory>
#include <cmath>

class Token;

#define NewToken(T) std::make_shared<Token>(T)

typedef std::shared_ptr<Token> SharedToken;
typedef std::vector<SharedToken> TokenVector;
typedef std::stack<SharedToken> TokenStack;

enum TokenTypes {
    UNDEFINED = 0,
    NUMBER = 1,
    FUNCTION = 2,
    OPERATOR = 3
};

class Token
{
    //sonlarni saqlash uchun
    double number_;
    
    //funksiyalarni saqlash uchun
    std::string function_;
    
    //operatorlarni saqlash uchun
    char op_;
    
    //Token qayti turga tegishli ekanligini aniqlash uchun
    TokenTypes type_;
    
    //bular yuqorida keltirilgan ustunliklar jadvali
    static std::map< char, int > op_precedence_;
    
public:
    Token(double n): number_(n) {type_ = NUMBER;}
    Token(std::string f): function_(f) {type_ = FUNCTION;}
    Token(char c): op_(c) {type_ = OPERATOR;}
    
    bool isOperator() { return type_ == OPERATOR; }
    bool isFunction() { return type_ == FUNCTION; }
    bool isNumber() { return type_ == NUMBER; }
    
    //ushbu funksiya qaysi matematik operator o'ng tarafdan boshlab hisoblanishini
    //aniqlash uchun qo'llaniladi. Bizning holatda faqat darajaga ko'tarish
    //o'ng tarafdan bo'lgani uchun shu holat ko'rsatilgan
    bool isRightAssociativity() { return isOperator() && getOperator() == '^'; }
    
    double getNumber() { return number_; }
    std::string getFunction() { return function_; }
    char getOperator() { return op_; }
    
    TokenTypes getType() const { return type_; }
    
    //bu agar token operator bo'lsa
    //uning ustunligini qaytaradi
    int precedence() const {
        if (type_ != OPERATOR)
            return -1;
        
        return op_precedence_[op_];
    };
    
    std::string string() {
        if (isFunction())
            return function_;
        
        if (isOperator())
            return std::string(1, op_);
        
        if (isNumber())
            return std::to_string(number_);
        
        return "";
    }
};

//bu ustunlik jadvalini kiritish
std::map<char, int> Token::op_precedence_ = {
    {'(', -1},
    {'+', 2},
    {'-', 2},
    {'*', 3},
    {'/', 3},
    {'^', 4}
};

class RpnExpression
{
    //OUTPUT QUEUE
    TokenVector stack_;
    
public:
    //OUTPUT QUEUE ga TOKEN qo'shish
    void push (SharedToken t) {
        stack_.push_back (t);
    }
    
    //OUTPUT QUEUE dan TOKEN olish
    SharedToken pop () {
        SharedToken t = stack_.front ();
        stack_.erase (stack_.begin ());
        return t;
    }
    
    //OUTPUT QUEUE bo'shligini tekshirish
    bool empty () const { return stack_.empty (); }
    
    //OUTUPT QUEUE ni chiqarish
    void print() {
        for(auto k : stack_) {
            std::cout<<k->string()<<" ";
        }
        
        std::cout<<std::endl;
    }
};

class ShuntingYard {
    //bu matematik ifodani saqlaydi: 4 + 2 * 3
    std::string expr_;
    
    //Bu bizning OUTPUT QUEUE
    RpnExpression rpn_;
    
    //Bu OPERATOR STACK
    TokenStack op_stack_;
    
    //Bu ochiq qavslarni OPERATOR STACK ga qo'shadi
    //ya'ni [6]-shart bajarilsa chaqiriladi
    void handle_left_paren () {
        op_stack_.push (NewToken('('));
    }
    
    //bu yopiq qavs kelganda chaqiriladi
    //ya'ni [7] shart bajarilganda chaqiriladi
    void handle_right_paren () {
        //OPERATOR STACK yuqorisidagi TOKEN '(' bo'lgunga qadar
        //OUTPUT QUEUE ga qo'shamiz
        //ya'ni 7.1 ni bajaryabmiz
        while (!op_stack_.empty() && op_stack_.top ()->getOperator() != '(') {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        
        //Agar ochiq qavs uchramasa
        //[7.4] ni bajaryapmiz
        if (op_stack_.empty())
            throw std::domain_error("Ifoda not'g'ri kritilgan");
        
        // '(' ochilgan qavsni chiqarib tashlaymiz
        // ya'ni [7.2] ni bajaryabmiz
        op_stack_.pop ();
        
        //Agar eng yuqorisidagi funksiya bo'lsa
        //TOKEN ni OUTPUT QUEUE ga o'tkazamiz
        //ya'ni [7.3] ni bajaryabmiz
        if (op_stack_.top()->isFunction()) {
            rpn_.push(op_stack_.top());
            op_stack_.pop();
        }
    }
    
    //Agar funksiya parametri bo'luvchisi (vergul) kelsa
    //ya'ni [4]-shart bajarilsa chaqiriladi
    void handle_func_seperator() {
        //ochiq qavs uchragunga qadar OUTPUT QUEUE ga o'tkazamiz, OPERATOR STACK dan
        while (!op_stack_.empty() && op_stack_.top ()->getOperator() != '(') {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        
        //ifoda not'g'ri, chunki qavs ochilmagan
        if (op_stack_.empty())
            throw std::domain_error("Ifoda noto'g'ri kiritilgan");
    }
    
    //operator bo'lganda chaqiriladi
    //[5]-shart bajarilsa
    void handle_op(SharedToken t) {
        //agar OPERATOR STACK da qiymat bo'lsa
        //5.1 - qoida
        while(!op_stack_.empty() && ((!t->isRightAssociativity() && t->precedence() <= op_stack_.top()->precedence() /* 1-shart */) ||
              (t->isRightAssociativity() && t->precedence() < op_stack_.top()->precedence()) /* 2-shart */)) {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        
        //Tokenni OPERATOR STACK ga qo'shamiz
        //5.2
        op_stack_.push(t);
    }
    
public:
    //Bu RpnExpression ifodani hisoblab bo'lib qaytaradi
    RpnExpression getRpn() {
        //char * ko'rinishiga o'tkazamiz
        //sababi o'qish osonlashadi
        const char* token = expr_.c_str();
        
        //token bu POINTER *token bu expr_ ning bir BYTE qiymati
        while(token && *token) {
            //bu yerda *token qiymati space (probel, bo'shliq bo'lsa)
            while(*token && isspace(*token)) {
                ++token; //keyingi belgiga o'tamiz
            }
            
            //agar son kelib qolsa
            //[2]-shart bajarilganda
            if (isdigit(*token)) {
                //token POINTER dan barcha raqamlarni o'qib,
                //double tipiga o'tkazib OUTPUT QUEUE ga TOKEN ni
                //qo'shamiz
                char *next_token;
                rpn_.push(NewToken(strtod(token, &next_token)));
                token = next_token;
            }
            //Agar harf kelib qolsa, demak funksiya
            //[3]-shart bajarilganda
            else if (isalpha(*token)) {
                std::stringstream func;
                do {
                    func<<*token;
                    ++token;
                }while(isalpha(*token));
                
                //va funksiyani OPERATOR STACK ga qo'shamiz
                op_stack_.push(NewToken(func.str()));
            } else {
                //funksiya bo'lmasa, son bo'lmasa
                //bitta belgini olib
                char op = *token;
                switch(op) {
                    case '(': //[6]-shart
                        handle_left_paren();
                        break;
                    case ')'://[7]-shart
                        handle_right_paren();
                        break;
                    case ','://[4]-shart
                        handle_func_seperator();
                        break;
                    default://qolgan holatlarda
                        handle_op(NewToken(op));
                        break;
                }
                
                ++token;
            }
        }
        
        //expr_ ni o'qib bo'lgandan keyin, OPERATOR STACK da qiymat bo'lsa
        //[8]-shart
        
        //[8.1]-shart
        if (!op_stack_.empty()) {
            if (op_stack_.top()->getOperator() == '(')
                std::domain_error("Ifoda not'g'ri");
        }
        
        //[8.2]-shart
        while (! op_stack_.empty ()) {
            rpn_.push (op_stack_.top ());
            op_stack_.pop ();
        }
        
        return rpn_;
    }
    
public:
    ShuntingYard(const std::string &expr):
    expr_(expr) {
        
    }
};

class Calculator {
    //bu double array, qiymatlar shunda saqlanadi
    std::stack< double > operands_;
    
    //qiymat chiqarish
    double pop () {
        double d = operands_.top ();
        operands_.pop ();
        return d;
    }
    
    //qiymat qo'shish
    void push (double d) {
        operands_.push (d);
    }
    
    //tozalash
    void flush () {
        while (! operands_.empty ()) { operands_.pop (); }
    }
    
    //Agar TOKEN number bo'lsa
    //ushbu funksiya chaqiriladi va yuqorida aytilganidek
    //massivga faqat qo'shiladi
    //[1.1] shart
    void consume(double value) {
        push (value);
    }
    
    //agar TOKEN funksiya bo'lsa chaqiriladi
    //[1.2] va [1.2.1] shartlar
    void consume(std::string func) {
        if (func == "sin") {
            push(sin(pop())); //[1.2.2] shart
        } else if (func == "max") {
            double v1 = pop();
            double v2 = pop();
            push(v1 > v2 ? v1 : v2); //[1.2.2] shart
        } else if (func == "sqrt") {
            push(sqrt(pop()));
        } else if (func == "cos") {
            push(cos(pop())); //[1.2.2] shart
        } else {
            throw std::domain_error("Funksiya mavjud emas: " + func);
        }
    }
    
    //Ahar TOKEN operator bo'lsa
    //[1.2] va [1.2.1] shartlar
    void consume(char op) {
        switch (op) {
            case '+':
                push (pop () + pop ()); //[1.2.2] shart
                break;
            case '*':
                push (pop () * pop ()); //[1.2.2] shart
                break;
            case '-':
            {
                double right = pop (); //[1.2.2] shart
                push (pop () - right);
            }
                break;
            case '/':
            {
                double right = pop ();
                if (right == 0)
                    throw std::domain_error("Qiymat 0 ga bo'linyapti");
                
                push (pop () / right); //[1.2.2] shart
            }
                break;
            case '^':
            {
                double right = pop ();
                push(pow(pop(), right)); //[1.2.2] shart
                break;
            }
            default:
                throw std::domain_error("Operator mavjud emas: " + std::string(1, op));
        }
    }
    
public:
    Calculator(RpnExpression& rpn) {
        //[1]-shart
        //rpn bo'sh qolguncha TOKEN larga mos
        //funksiyani chaqiramiz
        while(!rpn.empty()) {
            SharedToken t = rpn.pop();
            if (t->isNumber()) {
                consume(t->getNumber());
            } else if (t->isOperator()) {
                consume(t->getOperator());
            } else if (t->isFunction()) {
                consume(t->getFunction());
            }
        }
    }
    
    double result () const {
        return operands_.top ();
    }
};

int main() {
    ShuntingYard shunting("5 * (cos(1) ^ 2 + sim(1) ^ 2) / 2 + 10 - 3 ^ 2 + max(sqrt(25), sqrt(36))");
    auto rpn = shunting.getRpn();
    rpn.print();
    
    Calculator calc(rpn);
    
    std::cout<<std::endl<<"Natija: "<<calc.result()<<std::endl;
    
    return 0;
}