G2A Many GEOs
SHARE
TWEET

Arithmetic Expression : C++ Solution by Kristijan Burnik

kburnik Jan 31st, 2012 600 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Task: Arithmetic Expression
  3.    
  4.           Calculate value of an nonnegative integer arithmetic expression given
  5.           as a string and supporting + * / % (- excluded for simplicity)
  6.           Ignore all charachters which ar not a digit or an operation (+ * / %)
  7.           also detect division by zero and invalid or empty expression!
  8.              
  9.     Solution: Kristijan Burnik, Udruga informatičara Božo Težak
  10.               GMail: kristijanburnik
  11.              
  12.     Complexity: Three passes
  13.         Step 2: o(N) - Linear : where N denotes length of string
  14.         Step 3: o(N~) - Linear : where N~ denotes number of tokens
  15.         Step 4: o(N~) - Linear : where N~ denotes number of tokens
  16.                         (rotating of tokens back/forth is o(1) )
  17.    
  18.     Strucutres: String, Vector & Double ended Queue
  19.    
  20.     Date: 31.01.2012.
  21.    
  22.     ----
  23.    
  24.     Test input  : 13 + 22 * 5 / 11 + 92 + 3%2
  25.     Test output : 116
  26.                  (exit code 0)
  27.  
  28.     Test input  :
  29.     Test output : Empty expression!
  30.                  (exit code -1)
  31.    
  32.     Test input  :  7 + + 5
  33.     Test output : Invalid expression!
  34.                  (exit code -2)
  35.        
  36.     Test input  : 7 / 0 + 5
  37.     Test output : Division by zero!
  38.                  (exit code -3)
  39.    
  40. */
  41. #include <iostream>
  42. #include <cstdlib>
  43. #include <vector>
  44. #include <queue>
  45.  
  46. using namespace std;
  47.  
  48. typedef long long int llint;
  49. typedef pair <int,string> token;
  50. #define Type first
  51. #define Value second
  52. #define mp make_pair
  53.  
  54. const int NUMBER = 0, OPERATION = 1, OTHER = 2;
  55.  
  56. int get_type(char c) {
  57.     if  (c >= '0' && c <= '9') return NUMBER;
  58.     if (c == '*' || c == '+' || c == '/' || c == '%' ) return OPERATION;
  59.     if (c == '~') return OPERATION; // sentinel
  60.     return OTHER;    
  61. }
  62.  
  63. // when operator a has greater priority than b
  64. bool greater_priority(token a, token b) {
  65.     return (( a.Value=="*" || a.Value=="/" || a.Value=="%" ) && b.Value == "+");
  66. }
  67.  
  68. // integer to string conversion
  69. string to_string(llint x) {
  70.     string s;
  71.     while (x > 0) {
  72.         s = (char)((x%10)+'0') + s;
  73.         x/=10;
  74.     }
  75.     return s;
  76. }
  77.  
  78. // string to integer conversion
  79. llint to_int(string s) {
  80.     llint x = 0;
  81.     for (int i = 0; i < s.size() ; i++ ) {
  82.          x = x*10 + ((llint)(s[i]-'0'));
  83.     }
  84.     return x;
  85. }
  86.  
  87. int main(void) {
  88.  
  89. ////////////////////////////////////////////////////////////////////////////////
  90. // STEP 1: input arithmetic expression: NON-NEG integers and + * / % operations
  91. ////////////////////////////////////////////////////////////////////////////////
  92.  
  93.     string s;
  94.     getline(cin,s);
  95.  
  96. ////////////////////////////////////////////////////////////////////////////////
  97. // STEP 2: tokenize the expression
  98. ////////////////////////////////////////////////////////////////////////////////
  99.  
  100.     // add sentinel operation ~
  101.     s += "~";    
  102.    
  103.     bool found_numbers = false;
  104.     vector < token > tokens;
  105.     string buffer;
  106.     for (int i = 0; i  < s.size(); i++) {
  107.         char c = s[i];
  108.         int type = get_type(c);
  109.         switch(type) {
  110.             case NUMBER:
  111.                 buffer += c;
  112.                 found_numbers = true;
  113.             break;
  114.             case OPERATION:
  115.                 if (!found_numbers) {
  116.                     cout << "Empty expression!" << endl;
  117.                     exit(-1);    
  118.                 }
  119.                 if (buffer.size() > 0) {
  120.                     tokens.push_back(mp(NUMBER,buffer));
  121.                     buffer = "";
  122.                 }
  123.                 tokens.push_back(mp(OPERATION,s.substr(i,1)));
  124.                    
  125.             break;  
  126.         }
  127.         int ts = tokens.size();
  128.         if (ts > 1 && tokens[ts-1].Type == tokens[ts-2].Type) {
  129.             cout << "Invalid expression!" << endl;
  130.             exit(-2);    
  131.         }
  132.     }
  133.      
  134.      // remove the sentinel operation ~
  135.      tokens.pop_back();
  136.  
  137. ////////////////////////////////////////////////////////////////////////////////
  138. // STEP 3: Derive infix to sufix notation with priority handling!
  139. ////////////////////////////////////////////////////////////////////////////////
  140.  
  141.     deque <token> calc,ops;
  142.     string last_op;
  143.     for (int i = 0; i < tokens.size(); i++) {
  144.             calc.push_back(tokens[i]);
  145.             int cs = calc.size();
  146.            
  147.             switch (tokens[i].Type) {
  148.                 case NUMBER:
  149.                     if (last_op != "") {
  150.                         swap(calc[cs-1],calc[cs-2]);
  151.                         last_op = "";
  152.                     }
  153.                 break;
  154.                 case OPERATION:
  155.                     last_op = tokens[i].Value;
  156.                     ops.push_back(tokens[i]);
  157.                 break;    
  158.             }
  159.            
  160.             int os = ops.size();
  161.            
  162.             // handle priority if needed
  163.             if ( os > 1 && tokens[i].Type == NUMBER ) {
  164.                 if (greater_priority( ops[os-1], ops[os-2] ) ) {
  165.                     swap( calc[cs-3] , calc[cs-2]);                        
  166.                     swap( calc[cs-2] , calc[cs-1]);
  167.                     swap( ops[os-1], ops[os-2] );
  168.                 }    
  169.             }
  170.     }
  171.  
  172.  
  173. ////////////////////////////////////////////////////////////////////////////////
  174. // STEP 4: Calculate the expression from the sufix denoted tokens
  175. ////////////////////////////////////////////////////////////////////////////////
  176.  
  177.     token a, b, op, result = mp(NUMBER,"0");
  178.     int atback = 0;
  179.     while (calc.size() > 1) {
  180.          
  181.         // obtain first three tokens ( hope for A B OP respectivley )
  182.         a = calc[0]; // first operand
  183.         b = calc[1]; // second operand
  184.         op = calc[2]; // operation
  185.        
  186.         // Check if A, B and OP correspond to their expected token type:
  187.         // Priority handling: keep waiting operands at end of dequeue if needed
  188.         if (op.Type != OPERATION) {
  189.             // move the waiting operand to end of dequeue, and skip this round
  190.             calc.push_back(a);
  191.             calc.pop_front();
  192.            
  193.             // keep track of the waiting operands: will restore them after calc
  194.             atback++;
  195.            
  196.         } else {
  197.            // ready for calculating result, remove the front A, B and OP
  198.             calc.pop_front(); calc.pop_front(); calc.pop_front();
  199.  
  200.             // the essence of the calculation is done here
  201.             if (op.Value == "*") {
  202.                 result.Value = to_string( to_int(a.Value) * to_int(b.Value) );
  203.             } else if (op.Value == "+") {
  204.                 result.Value = to_string( to_int(a.Value) + to_int(b.Value) );
  205.             } else {
  206.                 // check for division by zero
  207.                 if (to_int(b.Value) == 0) {
  208.                     cout << "Division by zero!" << endl;
  209.                     exit(-3);
  210.                 }
  211.                 if (op.Value == "/") {
  212.                     result.Value = to_string( to_int(a.Value) / to_int(b.Value) );
  213.                 } else if (op.Value == "%") {
  214.                     result.Value = to_string( to_int(a.Value) % to_int(b.Value) );                
  215.                 }
  216.         }
  217.            
  218.             // insert the result to its place for rest of the calculation
  219.             calc.push_front(result);
  220.            
  221.             // restore the waiting operands from back to front
  222.             while (atback-- > 0) {
  223.                     calc.push_front(calc.back());
  224.                     calc.pop_back();
  225.             }
  226.             atback = 0;
  227.        
  228.         }
  229.        
  230.     }
  231.    
  232. ////////////////////////////////////////////////////////////////////////////////
  233. // STEP 5: output result  
  234. ////////////////////////////////////////////////////////////////////////////////
  235.  
  236.     cout << calc.front().Value << endl;
  237.  
  238.     return 0;
  239. }
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top