Question

For this assignment, implement a simple stack calculator which can compute an infix expression. It should take in a string containing an infix expression, compute the result, and print it out. It should handle operators +, -, *, / and parenthesis.

Your program must have two main steps -- first convert the expression to postfix, and then compute the result using the algorithms discussed in class and textbook. These algorithms require that you use a stack. You must implement your own stack, you may not use a library that implements a stack. No credit will be given if you don't implement your own stack.

Although your textbook contains implementations of a stack, I encourage you to try and implement your own stack, using the textbook as a reference if you need it. You can keep your stack simple if you wish -- e.g. it doesn’t need to be templated, it can just hold a simple data type like char. Additionally, it doesn’t need to handle error conditions because we are guaranteed a string containing a syntactically correct infix expression. You may implement either an array-based stack or a link-based stack.

To keep things simple, you may make the following assumptions:

- there are no spaces or other whitespace in the string

- all the operands are single digits

- the result of every operation is a single digit. For example, 2+3 is allowed because the result is 5. 5*3 is not allowed because the result is 15, which is two digits. 5+3+4 is not allowed because even though the first operation is 8, a single digit, the result of the second operation is 12, two digits. 5+3-4 is allowed because the result of the first operation is 8, and the result of the second operation is 4

- any string entered contains a valid, syntactically correct infix expression with balanced parenthesis (if any)

Conversion between int and char

The expression contains both char and int data, because each operator is a char and each operand is a digit. The easiest way to handle this is to implement a stack which supports char data. Since we know all our operands are single digits, we can simply push the character representing the digit onto the stack. Note this character will be the ASCII value of the character, not the integer value! As an example, the character '7' is ASCII value 55, '8' is 56, etc. If you need the actual integer value of the character, in this case 7, there is a convenient way to determine it. You can subtract the ASCII value of zero, '0' from the character. For example,, the following code will store 7 in i:

char c = '7';

int i = c - '0';

To get the character back, you can add '0' to an integer.

Extra Credit

For up to 10% extra credit, modify your program to remove the assumption that the string contains a valid, syntactically correct infix expression. It should compute the value if the string is valid, and gracefully handle an invalid string.

Answer 1

#include<cstdio>

#include <cstdlib>

#include <cstring>

#include <stack>

#include <cctype>

using namespace std;

bool error;

// returns true if op2 has lower or equal priority than op1, false otherwise

bool hasLowerPriority(char op1, char op2) {

switch (op1) {

case '(': return false;

case '-': return op2 == '-';

case '+': return op2 == '-' || op2 == '+';

case '*': return op2 != '/';

case '/': return true;

default : error = true; return false;

}

}

stack < char > operators;

stack < int > operands;

// perform the operation 'op' on the two operands on top of the stack

void operation(char op) {

if(operands.size() < 2) {

error = true; return;

}

int op2 = operands.top(); operands.pop();

int op1 = operands.top(); operands.pop();

switch(op) {

case '+': operands.push(op1 + op2); break;

case '-': operands.push(op1 - op2); break;

case '*': operands.push(op1 * op2); break;

case '/': operands.push(op1 / op2); break;

default : error = true; return;

}

}

int main() {

char exp[1000], *p;

int len;

printf("\t\t\t\tCALCULATOR\n");

while(true) {

printf("\nEnter an expression (. to exit):\n");

scanf("%[^\n]%*c", exp);

if(exp[0] == '.') break;

len = strlen(exp);

if(len == 0) { getchar(); continue; }

exp[len] = ' '; exp[len + 1] = ')'; exp[len + 2] = '\0';

error = false;

operators.push('(');

p = strtok(exp, " ");

while(p && !error) {

if(isdigit(p[0]))

operands.push(atoi(p));

else switch(p[0]) {

case '(' : operators.push('('); break;

case ')' : while (!operators.empty() && !error && operators.top() != '(') {

operation(operators.top()); operators.pop();

}

if (!operators.empty())

operators.pop();

else

error = true;

break;

default : while(!operators.empty() && !error && hasLowerPriority(operators.top(), p[0])) {

operation(operators.top()); operators.pop();

}

operators.push(p[0]);

}

p = strtok(NULL, " ");

}

if(error || !operators.empty() || operands.size() != 1) {

printf("ERROR\n");

while(!operands.empty())

operands.pop();

while(!operators.empty())

operators.pop();

} else {

printf("%d\n", operands.top()); operands.pop();

}

}

return 0;

}