• API
• FAQ
• Tools
• Archive
daily pastebin goal
15%
SHARE
TWEET

# Arithmetic Expression : C++ Solution by Kristijan Burnik

kburnik Jan 31st, 2012 535 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
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.

Top