#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.
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;
const char* chi = &ch;
temp_num += atoi(chi);
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 == '/'){
// Push operator on stack.
} else if(ch == ')'){
// Pop number, pop operator, pop number.
// Push result onto stack.
}
}
Element popped = pop(stack);
cout << popped.operand;
terminate_stack(stack);
return 0;
}