Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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("")+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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement