analyze the running time of the following program in terms of the input size n which 5195877

Analyze the running time of the following program in terms of the input size n, which in this case is the number of symbols in the logical expression given as the input. Run your program on 3 randomly generated logic expression containing at least 100, 1000 and 10000 symbols to verify your running time analysis result.

#include
#include
#include
#include
using namespace std;

int findPrecedency(char c){
switch(c){
case '(':return 5;
case ')':return 4;
case '!':return 3;
case '-':return 2;
default:return 1;
}
return -1;// invalid operator
}
int main(){
//Two important stack
stack operatorStack;
stack operandStack;

char expression[10002];

cin >> expression;

for(int i = 0; expression[i] != '0'; ++i){
//if left parenthesis push into operator stack
if(expression[i] == '('){
operatorStack.push('(');
}
// if it is a number push into operand stack
else if(expression[i] == '0' || expression[i] == '1'){
operandStack.push((expression[i] == '0')?0:1);
}
else if(expression[i] == ')'){
while(!operatorStack.empty() && operatorStack.top() != '('){
char k = operatorStack.top();
operatorStack.pop();
if(k == '!'){ // pop only one operand
int a = operandStack.top();
a ^= 1;
operandStack.pop();
operandStack.push(a);
}else{
int a = operandStack.top();
operandStack.pop();
int b = operandStack.top();
operandStack.pop();

if(k == '+'){
a |= b;
}
else{
a &= b;
}
operandStack.push(a);// push after the operation
}
}
// now pop the left parenthesis
operatorStack.pop();
}
else{
while(!operatorStack.empty() && operatorStack.top() != '(' &&
findPrecedency(operatorStack.top()) > findPrecedency(expression[i])){
char k = operatorStack.top();
operatorStack.pop();
if(k == '!'){ // pop only one operand
int a = operandStack.top();
a ^= 1;
operandStack.pop();
operandStack.push(a);
}else{
int a = operandStack.top();
operandStack.pop();
int b = operandStack.top();
operandStack.pop();

if(k == '+'){
a |= b;
}
else{
a &= b;
}
operandStack.push(a);// push after the operation
}
}
operatorStack.push(expression[i]);
}
}
//empty the operator stack to get the value
  
while(!operatorStack.empty()){
char k = operatorStack.top();
operatorStack.pop();
if(k == '!'){ // pop only one operand
int a = operandStack.top();
a ^= 1;
operandStack.pop();
operandStack.push(a);
}else{
int a = operandStack.top();
operandStack.pop();
int b = operandStack.top();
operandStack.pop();

if(k == '+'){
a |= b;
}
else{
a &= b;
}
operandStack.push(a);// push after the operation
}
}
cout

return 0;

}

"Get 15% discount on your first 3 orders with us"
Use the following coupon
FIRST15

Order Now