#include <iostream>
#include <string> // For strings
#include <cctype> // Check digit
using namespace std;
// Element struct.
struct std_element {
char oper;
unsigned operand;
};
// Typedef lets us simply call it by saying Element
typedef struct std_element Element;
struct Node {
Element el;
Node *next; // Pointer to next node.
};
// Simply call it by saying Node.
typedef struct Node Node;
struct Stack {
Node *top; // Topmost node of the stack. LIFO
};
// Call by saying Stack.
typedef struct Stack Stack;
// Function prototypes.
// Creates a new stack, returns with top = null.
Stack *create_stack();
// Push the most recent element onto the stack.
void push(Stack *stack, Element recent_el);
// Pop and return the topmost Element from the stack.
Element pop(Stack *stack);
// Terminate the stack and free up some memory.
void terminate_stack(Stack *stack);
// Creates a new stack, returns with top = null.
Stack *create_stack(){
Stack *new_stack = (Stack*)malloc(sizeof(Stack));
new_stack->top = NULL;
return new_stack;
}
// Push the most recent element onto the stack.
// Checks if starting from very start or not.
void push(Stack *stack, Element recent_el){
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->el = recent_el;
newNode->next = NULL;
// If empty
if(stack->top == NULL){
stack->top = newNode;
} else {
// Push on top of stack.
newNode->next = stack->top;
stack->top = newNode;
}
}
// Pop and return the topmost Element from the stack.
Element pop(Stack *stack){
Node *temp;
// Check if stack is empty;
if(stack->top == NULL){
Element el_error;
el_error.oper = '#';
el_error.operand = 0;
return el_error;
}
// Remove top item and copy over data.
temp = stack->top;
stack->top = stack->top->next;
Element temp_el = temp->el;
// Free up memory.
free(temp);
return temp_el;
}
// Terminate the stack and free up all memory.
void terminate_stack(Stack *stack){
Node *temp_item;
// Check if is not empty.
if(!(stack->top == NULL)){
temp_item = stack->top;
// Loop through and free up all memory.
while(stack->top != NULL){
temp_item = stack->top;
stack->top = stack->top->next;
free(temp_item);
}
}
}
int main(int argc, char const *argv[]){
Stack* stack = create_stack();
cout << "Please enter a math expression: ";
string line; // Math expression is put into this.
getline(cin, line); // Gets one line.
int temp_num = 0; // Checks/sets up any numbers.
bool dividebyzero = false; // Set to true if we divide by zero.
for(unsigned int i = 0; i<line.length(); i++) {
char ch = line[i]; // Character
if(isdigit(ch)){
// Read number in and then push on stack.
temp_num *= 10;
int digit = ch - '0'; // We subtract by '0' in order to get the digit.
temp_num += digit;
if(!isdigit(line[i + 1])){ // Check next char in string and see if it's not a digit.
Element num_el;
num_el.oper = '#';
num_el.operand = temp_num;
push(stack, num_el);
temp_num = 0;
}
// Else it'll wait for next number to process that one.
} else if(ch == '+' || ch == '-' || ch == '*' || ch == '/'){
Element symbol_el;
symbol_el.oper = ch;
symbol_el.operand = 0;
push(stack, symbol_el);
} else if(ch == ')'){
// Pop number, pop operator, pop number.
// Push result onto stack.
Element num_1 = pop(stack);
Element oper = pop(stack);
Element num_2 = pop(stack);
Element result;
if(oper.oper == '/' && num_2.operand == 0){
// Gracefully handle divison by zero.
dividebyzero = true;
cout << "Division by zero." << endl;
break;
} else {
switch(oper.oper){
case '+':
result.oper = '#';
result.operand = num_1.operand + num_2.operand;
push(stack, result);
break;
case '-':
result.oper = '#';
result.operand = num_1.operand - num_2.operand;
push(stack, result);
break;
case '*':
result.oper = '#';
result.operand = num_1.operand * num_2.operand;
push(stack, result);
break;
case '/':
result.oper = '#';
result.operand = num_1.operand / num_2.operand;
push(stack, result);
break;
}
}
}
}
// Output result.
if(!dividebyzero){
Element result = pop(stack);
cout << "Result: " << result.operand << endl;
terminate_stack(stack);
} else {
cout << "Division by zero! This is invalid! Please check your expression." << endl;
}
return 0;
}