Unsolved Need some help while implementing RPN
-
I tried to implement this algorithm on c++. I tried almost 8 hrs. 2 hrs for understanding algorithm ,that it is very hard . But that was easy. And almost roughly 6 hours of coding.
I want to implement this in plain C++. And can usedeque
andvector
And this is not my homework or any task!!! I am just trying to learn something extra since I don't have machine to run higher stuff like QTI haven't visited any implementation before this of the same thing. I tried to implement it on JavaScript at first and I completed it but couldn't complete this in c++
If you are free then try compiling this
some cout are just for debugging purpose and try catch blocks are also for the same. I got tired of seeing this thing so posting here
ALSO rate my coding style out of 10
LOL#include <iostream> #include<vector> #include <string> #include <string.h> #include<algorithm> #include<cmath> #include<map> #include<deque> using std::cout,std::cin, std::string, std::endl; // THIS MUST BE COMPILED WITH C++17, Because comma separated value are supported with it // g++ main.cpp -std=c++17 #define LEFT_TO_RIGHT "LEFT_TO_RIGHT" #define RIGHT_TO_LEFT "RIGHT_TO_LEFT" // can use const too std::map<string,int> precedenceDeclaration; std::map<string,string> associativeDeclaration; void fillFirst(){ // precedenceDeclaration.insert(std::make_pair("(",0)); precedenceDeclaration.insert(std::make_pair("[",0)); precedenceDeclaration.insert(std::make_pair("{",0)); precedenceDeclaration.insert(std::make_pair("+",1)); precedenceDeclaration.insert(std::make_pair("-",1)); precedenceDeclaration.insert(std::make_pair("/",2)); precedenceDeclaration.insert(std::make_pair("*",2)); precedenceDeclaration.insert(std::make_pair("%",2)); precedenceDeclaration.insert(std::make_pair("^",3)); precedenceDeclaration.insert(std::make_pair(")",4)); precedenceDeclaration.insert(std::make_pair("}",4)); precedenceDeclaration.insert(std::make_pair("]",4)); associativeDeclaration.insert(std::make_pair("+",LEFT_TO_RIGHT)); associativeDeclaration.insert(std::make_pair("-",LEFT_TO_RIGHT)); associativeDeclaration.insert(std::make_pair("*",LEFT_TO_RIGHT)); associativeDeclaration.insert(std::make_pair("/",LEFT_TO_RIGHT)); associativeDeclaration.insert(std::make_pair("%",LEFT_TO_RIGHT)); associativeDeclaration.insert(std::make_pair("^",RIGHT_TO_LEFT)); } int precedence(string op){ if(precedenceDeclaration.count(op) < 1){ throw "character is invalid for precedence"; } return precedenceDeclaration[op]; } std::string associativity(string toFind){ if(associativeDeclaration.count(toFind) < 1){ throw "Character is invalid for associativity"; } return associativeDeclaration[toFind]; } bool isNumber(string value){ for(auto v : value){ if(std::isdigit(v) == false){ return false; } } return true; } std::string last(std::deque<string> arr){ if(arr.size() == 0 ){ throw "Cannot get the last element of empty structure"; // throw 10; } return arr.at(arr.size() - 1); } bool isValidCharacter(string value){ try{ if(precedence(value) >= 0){ return true; } }catch(string err){ std::cout<<err; std::cout<<"The character is not valid character!!!!!!!!!!"; } return false; } bool isValidOperator(string value){ try{ if(precedence(value) > 0 && precedence(value) < 4){ return true; } }catch(string err){ std::cout<<err; std::cout<<"The character is not valid operator!!!!!1"; } return false; } float convertToNumber(string str){ return atof(str.c_str()); } string convertToStringS(char s){ return string({s}); } float evaluateOperation(string op1 , char operatorInput, string op2){ float operand1 = convertToNumber(op1); float operand2 = convertToNumber(op2); switch(operatorInput){ case '+': return operand1 + operand2; break; case '-': return operand1 - operand2; break; } return 500; } template <typename Data> void display(Data val){ std::cout<<"\n{ "; for(auto v:val){ std::cout<<" '"<<v<<"',"; } std::cout<<" }"; } void RPN(string equation); int main(){ fillFirst(); string operation = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"; RPN(operation); } /* [ '3', '4', '2', '*', '+', '1', '5', '-', '2', '3', '^', '^', '/' ] */ void RPN(string equation){ std::deque<std::string> stack,output; for(auto eq:equation){ string currentCharacter = convertToStringS(eq); if(currentCharacter == " " || currentCharacter == "."){ continue; } if(isNumber(currentCharacter)){ output.push_back(currentCharacter); }else if(isValidCharacter(currentCharacter)){ std::cout<<"\nOperator = "<<currentCharacter<<std::endl; int currentPrecedence = precedence(currentCharacter); if(currentPrecedence == 0 ){ output.push_back(currentCharacter); }else if(currentPrecedence == 4){ while(precedence(last(stack)) != 0){ string lastStack = last(stack); stack.pop_back(); output.push_back(lastStack); if(stack.size() == 0 ){ break; } } if(stack.size() != 0){stack.pop_back(); display(stack);} } auto performBack = [&](){ if(stack.size() != 0){ while(currentPrecedence < precedence(last(stack))){ std::cout<<"inside performBack "<<std::endl; display(stack); display(output); if(stack.size() == 0 ) break; string lastWord = last(stack); output.push_back(lastWord); stack.pop_back(); } } stack.push_back(currentCharacter); }; ///////////////////////////////////////////////////////////////////////////////////////////////////////// THAT THROW IS JUST FOR CHECKING!!!!!!!!!!!!!!!! if(isValidOperator(currentCharacter)){ if(stack.size() == 0 ){ stack.push_back(currentCharacter); }else if(currentPrecedence > precedence(last(stack)) || precedence(last(stack)) == 0){ stack.push_back(currentCharacter); }else if(currentPrecedence < precedence(last(stack))){ performBack(); /* while(stack.size() != 0 || currentPrecedence > precedence(last(stack))){ string lastWord = last(stack); output.push_back(lastWord); stack.pop_back(); } */ }else if(currentPrecedence == precedence(last(stack))){ if(associativity(currentCharacter) == LEFT_TO_RIGHT){ performBack(); }else if(associativity(currentCharacter) == RIGHT_TO_LEFT){ stack.push_back(currentCharacter); } } } } display(output); display(stack); } }
-
Hello guys
@jsulm @mrjj @JonB @SGaist @AnneRanch
I hope to get some thoughts on this!