Analyze the running time of the following program in terms o

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 <iostream>
#include <stack>
#include <typeinfo>
#include <string>
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<char> operatorStack;
stack<int> 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 << operandStack.top() << endl;

return 0;

}

Solution

Time complexity O(n) as only single loops are used. In the for loop you used while loop, but not of size n(less number of iterations than for loop) and you have another for loop also which runs n times. So at the whole its O(n). When you stack also, every operatir is pushed only once nad popped once, as operators will be less than toltal number of tokens, i.e n. Nothing much time is taken

Space Complexity O(n), size of the expression