Please nominate your Qt Champions for 2021! https://forum.qt.io/topic/132134/looking-for-the-2021-qt-champions

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 use deque and vector
    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 QT

    I 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!


Log in to reply