shranet/ShuntingYard.cpp

## 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;
}
	//
	// 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;
	}