# Arithmetic Expression : C++ Solution by Kristijan Burnik

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

# Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×