/*
    Nitish Sarin
    Thapar University
 */

#include<iostream>
#include<cstring>
using namespace std;

void ConvertPostfix(char*);               // Takes the character array, and converts it to postfix
float EvaluatePostfix(char*);             // Asks you the values of the variables used at runtime and evaluates the infix expression
                                          // after converting it to postfix
float Calc(char, float, float);           // Performs the operation operator1 <operand> operator 2
bool Precedence(char, char);              // It will return whether operator1 has higher precedence than operator2
int Opweight(char);                       // Returns the relative weight of the operators based on precedence order
bool Operator(char);                      // Returns true if the given parameter belongs to { =, -, *, /, % } --> Left Associative
bool Operand(char);                       // Returns true if the given parameter belongs to { a-z OR A-Z )


char postfix[100];                        // Global array


class s{                                  // Class for character Stack
public:
	char arr[100];
	int top = -1;

	void pop(){                           // Pop out the top element from the stack
	if(empty()){
		cout<<"Array is empty"<<endl<<endl;
		return;
	}
	top--;
	}

	void show(){                          // Show the current status of the stack
	cout<<endl<<endl;
	if(empty()){
		cout<<"Array is empty"<<endl<<endl;
		return;
	}

	for(int i=0; i<=top; i++){
		cout<<arr[i]<<"  ";
	}

		cout<<endl<<endl;
	}

	bool empty(){                         // Returns true if the stack is empty
	if(top<0){
		return true;
	}
	return false;
	}

	void push(char data){                 // Push data into the stack
	top++;
	arr[top]=data;
	}

};

class cal{                                // Class for storing numerical operands in Stack
public:
	float arr[100];
	int top = -1;

	void pop(){
	if(top==-1){
		cout<<endl;
		cout<<"Array is empty"<<endl<<endl;
		return;
	}
	top--;
	}

	void show(){
	cout<<endl<<endl;
	if(top==-1){
		cout<<"Array is empty"<<endl<<endl;
		return;
	}

	for(int i=0; i<=top; i++){
		cout<<arr[i]<<"  ";
	}

		cout<<endl<<endl;
	}

	bool empty(){
	if(top<0){
		return true;
	}
	return false;
	}

	void push(char data){
	top++;
	arr[top]=data;
	}

};


int main(){
	int op;
	s st;
	char data;
	char infix[100];

                                             // ***************************User Interface******************************

	cout<<"Welcome to Stack Interface Arena!"<<endl<<endl;
	do{
		cout<<"1) Push an element into the Stack."<<endl;
		cout<<"2) Pop an element from the Stack."<<endl;
		cout<<"3) Show the current status of the Stack."<<endl;
		cout<<"4) Convert Infix to Postfix (Using BOMDAS rule)."<<endl;
		cout<<"5) Evaluate a given Infix expression by first converting it to Postfix."<<endl;
		cout<<"6) Exit";
		cin>>op;
		switch(op){
			case 1:
			cout<<"Please enter the element which you would like to push -->  ";
			cin>>data;
			st.push(data);
			break;
			case 2:
			st.pop();
			break;
			case 3:
			st.show();
			break;
			case 4:
			cout<<endl<<endl;
			cout<<"Only + - * / \% operators are allowed!!"<<endl;
			cout<<"Please enter the expression(Infix) -->  ";
			cin.ignore();																	// Ignore the \n character stored from the previous cin
			cin.getline(infix, 100);														// So that we can enter a line including spaces
			ConvertPostfix(infix);
			cout<<"The final Postfix form is  "<<postfix<<endl;
			break;
			case 5:
			cout<<"Please enter the expression(Infix) -->  ";
			cin.ignore();
			cin.getline(infix, 100);
			cout<< "The evaluated output is  "<<EvaluatePostfix(infix)<<endl;
			break;
			default:
			cout<<"Please enter a valid choice"<<endl;
		}
	cout<<"----------------------------------------------------"<<endl<<endl;
	}while(op!=6);

}


void ConvertPostfix(char* expression){														// Takes the character array, and converts it to postfix
	s st1;
	memset(&postfix[0], 0, sizeof(postfix));												// Flush out any previous stored data
	int j=0;
	for(int i=0; i<strlen(expression); i++){
		if(expression[i]==' '){															        	// Ignore the spaces
			continue;
		}

		else if(Operator(expression[i])){													    // If an operator, it is pushed into the stack after
																						                    	// popping out all higher precedence operators

			while(!st1.empty() && st1.arr[st1.top]!='(' && Precedence(st1.arr[st1.top], expression[i])){
				postfix[j]=st1.arr[st1.top];
				st1.pop();
				j++;
			}
			st1.push(expression[i]);
		}
		else if(Operand(expression[i])){													  // Appending operand to the postfix string
			postfix[j]=expression[i];
			j++;
		}
		else if(expression[i]=='('){
			st1.push(expression[i]);
		}

		else if(expression[i]==')'){													    	// pop out operators till opening bracket of the closed one is found
			while(!st1.empty() && st1.arr[st1.top]!= '('){
				postfix[j]=st1.arr[st1.top];
				j++;
				st1.pop();
			}
			if(!st1.empty()){
				st1.pop();
			}
		}
	}
	while(!st1.empty()){																	// Appending the rest of the stack to the postfix expression!
		postfix[j]=st1.arr[st1.top];
		j++;
		st1.pop();
	}
}

bool Operator(char op){																		// Returns true if the given parameter belongs to { =, -, *, /, % } --> Left Associative

	if(op == '+' || op == '-' || op == '*' || op == '/' || op== '%'){
		return true;
	}
	return false;
}

bool Operand(char op){																		// Returns true if the given parameter belongs to { a-z OR A-Z )

	if((op>='a' && op<='z') || (op>='A' && op <='Z')){
		return true;
	}
	return false;
}

bool Precedence(char op1, char op2){														// It will return whether operator1 has higher precedence than operator2
	int weight1= Opweight(op1);
	int weight2= Opweight(op2);

	if(weight1>=weight2){																	// As all operators are left associative
		return true;
	}
	return false;
}

int Opweight(char op){																		// Returns the relative weight of the operators based on precedence order
	int weight = -1;
	switch(op){
		case '-':
		case '+':
		weight = 1;
		break;
		case '/':
		case '*':
		case '%':
		weight = 2;
		break;
	}
	return weight;
}


float EvaluatePostfix(char* infix){															// Asks you the values of the variables used at runtime and evaluates the infix expression
                                          													// after converting it to postfix
	cal st;
	ConvertPostfix(infix);																	// First converting the infix to postfix before evaluating
	float eval=0, temp;
	for(int i=0; i<sizeof(postfix); i++){
		if(postfix[i] == ' '){
			continue;
		}
		else if(Operator(postfix[i])){
			float op2= st.arr[st.top];
			st.pop();
			float op1= st.arr[st.top];
			st.pop();
			float eval = Calc(postfix[i], op1, op2);										// Sending first two elements of stack, and the operator as arguments to the function
			st.push(eval);
		}
		else if(Operand(postfix[i])){
			cout<<" What value would you assign to the variable "<<postfix[i]<<" ? ";		// Asking the values of the  variables, at runtime!
			cin>>temp;
			st.push(temp);
		}
	}
	return st.arr[st.top];
}

float Calc(char op, float op1, float op2){													// Performs the operation operator1 <operand> operator 2
	if(op=='+'){
		return op1+op2;
	}
	else if(op=='-'){
		return op1-op2;
	}
	else if(op=='*'){
		return op1*op2;
	}
	else if(op=='/'){
		return op1/op2;
	}
	else if(op=='%'){
		return (int)op1 % (int)op2;
	}
	else{
		cout<< "Error! Please check the inputs Carefully"<<endl;
		return -1;
	}
}