Skip to content

Instantly share code, notes, and snippets.

@shranet shranet/ShuntingYard.cpp
Last active Nov 27, 2018

Embed
What would you like to do?
Shunting-yard with functions
//
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.