Advertisement
Guest User

Untitled

a guest
Jan 17th, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <string>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. class Parser {
  10. public:
  11. class Token {
  12. public:
  13. Token( string s ): data(s){;}
  14. bool isOperator(){
  15. if( data == "+" || data == "-" || data == "*" || data =="/" )
  16. return true;
  17. return false;
  18. }
  19. bool isNumber(){
  20. return !isOperator();
  21. }
  22. bool hasHigherPrecedenceThan( Token t ){
  23. if( precednceGroup[data] > precednceGroup[t.getValue()] ) return true;
  24. return false;
  25. }
  26. bool hasHigherOrEqualPrecedenceThan( Token t ){
  27. if( precednceGroup[data] >= precednceGroup[t.getValue()] ) return true;
  28. return false;
  29. }
  30. string getValue(){ return data; }
  31. private:
  32. string data;
  33. static map<string,int> precednceGroup;
  34. };
  35. Parser( string s ){
  36. for( auto c : s ){
  37. tokens.push_back( Token(string("")+c) );
  38. }
  39. };
  40. bool hasNextToken(){
  41. return !tokens.empty();
  42. }
  43. Token getNextToken(){
  44. Token token = tokens.front();
  45. tokens.pop_front();
  46. return token;
  47. }
  48. private:
  49. list<Token> tokens;
  50. };
  51.  
  52. map<string,int> Parser::Token::precednceGroup = {
  53. { "+", 1 }, {"-",1 }, { "*", 2 }, {"/",2}
  54. };
  55.  
  56.  
  57. string convert_arth( string s ){
  58. Parser parser(s);
  59. list<Parser::Token> opStack;
  60. string result;
  61. while( parser.hasNextToken() ){
  62. auto token = parser.getNextToken();
  63. if ( token.isNumber() ){
  64. result += token.getValue();
  65. }else
  66. if( opStack.empty() ){
  67. opStack.push_back(token);
  68. } else {
  69. auto oo = opStack.back();
  70. if( token.hasHigherPrecedenceThan( oo ) ){
  71. opStack.push_back(token);
  72. } else {
  73. while( !opStack.empty() ){
  74. auto oo = opStack.back();
  75. opStack.pop_back();
  76. result += oo.getValue();
  77. }
  78. opStack.push_back(token);
  79. }
  80. }
  81. }
  82. while( !opStack.empty() ){
  83. auto oo = opStack.back();
  84. opStack.pop_back();
  85. result += oo.getValue();
  86. }
  87. return result;
  88. }
  89.  
  90. string convert_arth2( string s ){
  91. Parser parser(s);
  92. list<Parser::Token> opStack;
  93. string result;
  94. while( parser.hasNextToken() ){
  95. auto token = parser.getNextToken();
  96. if ( token.isNumber() ){
  97. result += token.getValue();
  98. }else
  99. if( opStack.empty() ){
  100. opStack.push_back(token);
  101. } else {
  102. auto oo = opStack.back();
  103. if( token.hasHigherOrEqualPrecedenceThan( oo ) ){
  104. opStack.push_back(token);
  105. } else {
  106. while( !opStack.empty() ){
  107. auto oo = opStack.back();
  108. opStack.pop_back();
  109. result += oo.getValue();
  110. }
  111. opStack.push_back(token);
  112. }
  113. }
  114. }
  115. while( !opStack.empty() ){
  116. auto oo = opStack.back();
  117. opStack.pop_back();
  118. result += oo.getValue();
  119. }
  120. return result;
  121. }
  122.  
  123. string convert_arth3( string s ){
  124. Parser parser(s);
  125. list<Parser::Token> opStack;
  126. string result;
  127. while( parser.hasNextToken() ){
  128. auto token = parser.getNextToken();
  129. if ( token.isNumber() ){
  130. result += token.getValue();
  131. }else
  132. if( opStack.empty() ){
  133. opStack.push_back(token);
  134. } else {
  135. auto oo = opStack.back();
  136. if( token.hasHigherPrecedenceThan( oo ) ){
  137. opStack.push_back(token);
  138. } else {
  139. while( !opStack.empty() && !token.hasHigherPrecedenceThan(opStack.back())){
  140. auto oo = opStack.back();
  141. opStack.pop_back();
  142. result += oo.getValue();
  143. }
  144. opStack.push_back(token);
  145. }
  146. }
  147. }
  148. while( !opStack.empty() ){
  149. auto oo = opStack.back();
  150. opStack.pop_back();
  151. result += oo.getValue();
  152. }
  153. return result;
  154. }
  155.  
  156. string convert_arth4( string s ){
  157. Parser parser(s);
  158. list<Parser::Token> opStack;
  159. string result;
  160. while( parser.hasNextToken() ){
  161. auto token = parser.getNextToken();
  162. if ( token.isNumber() ){
  163. result += token.getValue();
  164. }else
  165. if( opStack.empty() ){
  166. opStack.push_back(token);
  167. } else {
  168. while( !opStack.empty() ){
  169. auto oo = opStack.back();
  170. if( token.hasHigherPrecedenceThan( oo ) ){
  171. break;
  172. } else {
  173. result += oo.getValue();
  174. opStack.pop_back();
  175. }
  176. }
  177. opStack.push_back( token );
  178. }
  179. }
  180. while( !opStack.empty() ){
  181. auto oo = opStack.back();
  182. opStack.pop_back();
  183. result += oo.getValue();
  184. }
  185. return result;
  186. }
  187.  
  188.  
  189. int main(){
  190. string s1("1+2-3*4/5*6+7");
  191. cout<< "org : " << s1<<endl;
  192. cout<< "case1 : " << convert_arth(s1) <<endl;
  193. cout<< "case2 : " << convert_arth2(s1) <<endl;
  194. cout<< "case3 : " << convert_arth3(s1) <<endl;
  195. cout<< "case4 : " << convert_arth4(s1) <<endl;
  196.  
  197. // RESULT
  198. // org : 1+2-3*4/5*6+7
  199. // case1 : 12+34*-5/6*7+
  200. // case2 : 123456*/*-+7+
  201. // case3 : 12+34*5/6*-7+
  202. // case4 : 12+34*5/6*-7+
  203. //
  204. return 0;
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement