daily pastebin goal
76%
SHARE
TWEET

Arithmetic Expression : C++ Solution by Kristijan Burnik

kburnik Jan 31st, 2012 530 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
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