Create a C++ program that can evaluate arithmetic expressions using stack with i
ID: 3723221 • Letter: C
Question
Create a C++ program that can evaluate arithmetic expressions using stack with integer numbers having any number of digits. These numbers are an alternative to fixed size integers or floating point numbers that always have a maximum number of accurate digits (dependent on size of CPU register).
The program should display the input expression and the results, separated with =. If one expression is not valid, skip it and continue to process next expression
input example :
0*00000000000000000+0000000000000001
(1+2)*(1000+2000)
output example:
0*00000000000000000+0000000000000001 = 1
(1+2)*(1000+2000) = 9000
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
typedef long long int llint;
typedef pair <int,string> token;
#define Type first
#define Value second
#define mp make_pair
const int NUMBER = 0, OPERATION = 1, OTHER = 2;
int get_type(char c)
{
if (c >= '0' && c <= '9')
return NUMBER;
if (c == '*' || c == '+' || c == '/' || c == '%' )
return OPERATION;
if (c == '~')
return OPERATION; // sentinel
return OTHER;
}
// when operator a has greater priority than b
bool greater_priority(token a, token b)
{
return (( a.Value=="*" || a.Value=="/" || a.Value=="%" ) && b.Value == "+");
}
// integer to string conversion
string to_string(llint x)
{
string s;
while (x > 0)
{
s = (char)((x%10)+'0') + s;
x/=10;
}
return s;
}
// string to integer conversion
llint to_int(string s)
{
llint x = 0;
for (int i = 0; i < s.size() ; i++ )
{
x = x*10 + ((llint)(s[i]-'0'));
}
return x;
}
int main(void)
{
string s;
getline(cin,s);
s += "~";
bool found_numbers = false;
vector < token > tokens;
string buffer;
for (int i = 0; i < s.size(); i++)
{
char c = s[i];
int type = get_type(c);
switch(type)
{
case NUMBER:
buffer += c;
found_numbers = true;
break;
case OPERATION:
if (!found_numbers)
{
cout << "Empty expression!" << endl;
exit(-1);
}
if (buffer.size() > 0)
{
tokens.push_back(mp(NUMBER,buffer));
buffer = "";
}
tokens.push_back(mp(OPERATION,s.substr(i,1)));
break;
}
int ts = tokens.size();
if (ts > 1 && tokens[ts-1].Type == tokens[ts-2].Type)
{
cout << "Invalid expression!" << endl;
exit(-2);
}
}
tokens.pop_back();
deque <token> calc,ops;
string last_op;
for (int i = 0; i < tokens.size(); i++)
{
calc.push_back(tokens[i]);
int cs = calc.size();
switch (tokens[i].Type)
{
case NUMBER:
if (last_op != "")
{
swap(calc[cs-1],calc[cs-2]);
last_op = "";
}
break;
case OPERATION:
last_op = tokens[i].Value;
ops.push_back(tokens[i]);
break;
}
int os = ops.size();
if ( os > 1 && tokens[i].Type == NUMBER )
{
if (greater_priority( ops[os-1], ops[os-2] ) )
{
swap( calc[cs-3] , calc[cs-2]);
swap( calc[cs-2] , calc[cs-1]);
swap( ops[os-1], ops[os-2] );
}
}
}
token a, b, op, result = mp(NUMBER,"0");
int atback = 0;
while (calc.size() > 1)
{
// obtain first three tokens ( hope for A B OP respectivley )
a = calc[0]; // first operand
b = calc[1]; // second operand
op = calc[2]; // operation
if (op.Type != OPERATION)
{
// move the waiting operand to end of dequeue, and skip this round
calc.push_back(a);
calc.pop_front();
atback++;
} else
{
calc.pop_front(); calc.pop_front(); calc.pop_front();
// the essence of the calculation is done here
if (op.Value == "*")
{
result.Value = to_string( to_int(a.Value) * to_int(b.Value) );
}
else if (op.Value == "+")
{
result.Value = to_string( to_int(a.Value) + to_int(b.Value) );
} else
{
// check for division by zero
if (to_int(b.Value) == 0)
{
cout << "Division by zero!" << endl;
exit(-3);
}
if (op.Value == "/")
{
result.Value = to_string( to_int(a.Value) / to_int(b.Value) );
}
else if (op.Value == "%")
{
result.Value = to_string( to_int(a.Value) % to_int(b.Value) );
}
}
// insert the result to its place for rest of the calculation
calc.push_front(result);
while (atback-- > 0)
{
calc.push_front(calc.back());
calc.pop_back();
}
atback = 0;
}
}
cout << calc.front().Value << endl;
return 0;
}