convertToPostFix.cxx

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <map>

using namespace std;

class Parser {
public:
  class Token {
  public:
    Token( string s ): data(s){;}
    bool isOperator(){
      if( data == "+" || data == "-" || data == "*" || data =="/" ) 
        return true;
      return false;
    }
    bool isNumber(){
      return !isOperator();
    }
    bool hasHigherPrecedenceThan( Token t ){
      if( precednceGroup[data] > precednceGroup[t.getValue()] ) return true;
      return false;
    }
    bool hasHigherOrEqualPrecedenceThan( Token t ){
      if( precednceGroup[data] >= precednceGroup[t.getValue()] ) return true;
      return false;
    }
    string getValue(){ return data; }
  private:
    string data;
    static map<string,int> precednceGroup;
  };
  Parser( string s ){
    for( auto c : s ){
      tokens.push_back( Token(string(1,c)) );
    }
  };
  bool hasNextToken(){
    return !tokens.empty();
  }
  Token getNextToken(){
    Token token = tokens.front();
    tokens.pop_front();
    return token;
  }
private:
  list<Token> tokens;
};

map<string,int> Parser::Token::precednceGroup = { 
  { "+", 1 }, {"-",1 }, { "*", 2 }, {"/",2}
};


string convert_arth( string s ){
  Parser parser(s);
  list<Parser::Token> opStack;
  string result;
  while( parser.hasNextToken() ){
    auto token = parser.getNextToken();  
    if ( token.isNumber() ){
      result += token.getValue();
    }else
      if( opStack.empty() ){
        opStack.push_back(token);
      } else { 
        auto oo = opStack.back();
        if( token.hasHigherPrecedenceThan( oo ) ){
          opStack.push_back(token);
        } else {
          while( !opStack.empty() ){
            auto oo = opStack.back();
            opStack.pop_back();
            result += oo.getValue();
          }
          opStack.push_back(token);
        }
      }
  }
  while( !opStack.empty() ){
    auto oo = opStack.back();
    opStack.pop_back();
    result += oo.getValue();
  }
  return result;
}

string convert_arth2( string s ){
  Parser parser(s);
  list<Parser::Token> opStack;
  string result;
  while( parser.hasNextToken() ){
    auto token = parser.getNextToken();  
    if ( token.isNumber() ){
      result += token.getValue();
    }else
      if( opStack.empty() ){
        opStack.push_back(token);
      } else { 
        auto oo = opStack.back();
        if( token.hasHigherOrEqualPrecedenceThan( oo ) ){
          opStack.push_back(token);
        } else {
          while( !opStack.empty() ){
            auto oo = opStack.back();
            opStack.pop_back();
            result += oo.getValue();
          }
          opStack.push_back(token);
        }
      }
  }
  while( !opStack.empty() ){
    auto oo = opStack.back();
    opStack.pop_back();
    result += oo.getValue();
  }
  return result;
}

string convert_arth3( string s ){
  Parser parser(s);
  list<Parser::Token> opStack;
  string result;
  while( parser.hasNextToken() ){
    auto token = parser.getNextToken();  
    if ( token.isNumber() ){
      result += token.getValue();
    }else
      if( opStack.empty() ){
        opStack.push_back(token);
      } else { 
        auto oo = opStack.back();
        if( token.hasHigherPrecedenceThan( oo ) ){
          opStack.push_back(token);
        } else {
          while( !opStack.empty() && !token.hasHigherPrecedenceThan(opStack.back())){
            auto oo = opStack.back();
            opStack.pop_back();
            result += oo.getValue();
          }
          opStack.push_back(token);
        }
      }
  }
  while( !opStack.empty() ){
    auto oo = opStack.back();
    opStack.pop_back();
    result += oo.getValue();
  }
  return result;
}

string convert_arth4( string s ){
  Parser parser(s);
  list<Parser::Token> opStack;
  string result;
  while( parser.hasNextToken() ){
    auto token = parser.getNextToken();  
    if ( token.isNumber() ){
      result += token.getValue();
    }else
      if( opStack.empty() ){
        opStack.push_back(token);
      } else { 
        while( !opStack.empty() ){
          auto oo = opStack.back();
          if( token.hasHigherPrecedenceThan( oo ) ){
            break;
          } else {
            result += oo.getValue();
            opStack.pop_back();
          }
        }
        opStack.push_back( token ); 
      }
  }
  while( !opStack.empty() ){
    auto oo = opStack.back();
    opStack.pop_back();
    result += oo.getValue();
  }
  return result;
}


int main(){
  string s1("1+2-3*4/5*6+7");
  cout<< "org   : " << s1<<endl;
  cout<< "case1 : " << convert_arth(s1) <<endl;
  cout<< "case2 : " << convert_arth2(s1) <<endl;
  cout<< "case3 : " << convert_arth3(s1) <<endl;
  cout<< "case4 : " << convert_arth4(s1) <<endl;

  // RESULT
  // org   : 1+2-3*4/5*6+7
  // case1 : 12+34*-5/6*7+
  // case2 : 123456*/*-+7+
  // case3 : 12+34*5/6*-7+
  // case4 : 12+34*5/6*-7+
  //
  return 0;
}