Stack based recursive arithmetic expression parser

Question

I recently started to learn C++ and came across this problem in a book "Object Oriented Programming in C++" by Robert Lafore.

The author has a program in the book which creates a Parser. I found a problem with the original program in the book which breaks at one of the input expressions I am providing. Therefore I tried to make changes and made it recursive. It works fine with the inputs I am providing.

I am more concerned about correctness and programming style of the program I have written. I believe I have made many mistakes. Any comments would be very helpful.

#include <iostream> using namespace std; const char SIZE = 40; class Stack { private: char array[SIZE]; char top; public: Stack():top(-1) { } void push(char v) { if (!is_full()) { array[++top] = v; } } char pop() { if (!is_empty()) { return array[top--]; } throw "Stack is empty. Pop failed"; } bool is_full() { return top >= SIZE ? true : false; } bool is_empty() { return top == -1; } char get_top() { return top; } }; bool is_operator(char c) { return (c == '*' || c == '/' || c == '+' || c == '-'); } bool is_dm_operator(char c) { return (c == '*' || c == '/'); } bool is_value(char c) { return (c >= '0' && c <= '9'); } void resolve_op_recursively(Stack& e_stack, char in) { if (e_stack.get_top() == 0) //stack has only 1 operand { e_stack.push(in); } else { char last_val = e_stack.pop(); char last_op = e_stack.pop(); if (is_dm_operator(in) && !is_dm_operator(last_op)) // 2 + 3 * 5 case only { e_stack.push(last_op); e_stack.push(last_val); e_stack.push(in); } else { char first_val = e_stack.pop(); switch (last_op) { case '/': e_stack.push(first_val / last_val); break; case '*': e_stack.push(first_val * last_val); break; case '+': e_stack.push(first_val + last_val); break; case '-': e_stack.push(first_val - last_val); break; default: break; } resolve_op_recursively(e_stack, in); } } } void parse_expression_using_stack(Stack& e_stack, const char * input) { while (*input) { char in = *input; if (in != ' ') { if (is_value(in)) { e_stack.push(in - '0'); } else if (is_operator(in)) { resolve_op_recursively(e_stack, in); } else { cout << "unknow expression" << endl; } } input++; } } void solve_expression_using_stack(Stack& e_stack) { while(e_stack.get_top()) { char second_operand = e_stack.pop(); char operator_ = e_stack.pop(); switch (operator_) { case '+': e_stack.push(e_stack.pop() + second_operand); break; case '-': e_stack.push(e_stack.pop() - second_operand); break; case '*': e_stack.push(e_stack.pop() * second_operand); break; case '/': e_stack.push(e_stack.pop() / second_operand); break; default: cout << "unkown operand " << operator_ << endl; } } } void solve_expression_and_match_result(const char * input, char expected_result) { Stack e_stack; char result; cout << "Expression: " << input; parse_expression_using_stack(e_stack, input); solve_expression_using_stack(e_stack); result = e_stack.pop(); cout << " Got solution: " << static_cast<int>(result) << " Expected Solution: " << static_cast<int>(expected_result) << " Test: "; if (result == expected_result) { cout << "\nPASSED" << endl; } else { cout << "\nFAILED" << endl; } } int main(int argc, const char * argv[]) { const char * expressions[20] = { static_cast<const char *>("5 / 5 + 3 - 6 * 2"), // why static_cast here? what is const_cast static_cast<const char *>("3 * 7 - 1 + 5 / 3"), static_cast<const char *>("3 * 5 - 4"), static_cast<const char *>("3 + 5 - 4"), static_cast<const char *>("2 / 6 * 3 / 2"), static_cast<const char *>("3 + 6 * 9 / 3 - 7"), static_cast<const char *>("9 - 5 / 5 * 2 + 6"), static_cast<const char *>("7 + 3 * 4 / 2 - 5 * 6"), static_cast<const char *>("4 * 5 + 3 - 4 / 2"), static_cast<const char *>("4 / 2 * 5 + 3 - 4"), static_cast<const char *>("5 + 3 * 4 / 2 - 3"), static_cast<const char *>("5 - 3 + 4 / 2"), static_cast<const char *>("5 * 3 / 2 - 2"), static_cast<const char *>("5 * 2 / 4 + 9 - 2") }; char solutions[20] = { 5 / 5 + 3 - 6 * 2, 3 * 7 - 1 + 5 / 3, 3 * 5 - 4, 3 + 5 - 4, 2 / 6 * 3 / 2, 3 + 6 * 9 / 3 - 7, 9 - 5 / 5 * 2 + 6, 7 + 3 * 4 / 2 - 5 * 6, 4 * 5 + 3 - 4 / 2, 4 / 2 * 5 + 3 - 4, 5 + 3 * 4 / 2 - 3, 5 - 3 + 4 / 2, 5 * 3 / 2 - 2, 5 * 2 / 4 + 9 - 2 }; for (int i = 0; i < 20; ++i) { if (expressions[i]) { solve_expression_and_match_result(expressions[i], solutions[i]); } } return 0; } 

Answer 1

1. Don't use using namespace std;

While that would work in your particular case, it's considered bad practice. Especially when you move out your code to separate header files.

See more details here please:

Why is “using namespace std;” considered bad practice?

2. Don't reinvent the wheel

You shouldn't write your own stack class, in preference of just using what the C++ standard library already provides.

There's already std::stack, that should work well for your needs.

3. Don't use raw arrays in C++

Your raw array

char array[SIZE]; 

should be a

std::array<char,SIZE> arr; 

instead. std::array would cover all your needs, and gives you a more safe implementation.

Also the naming array might clash with the using namespace std; as mentioned.

4. Don't use throw with types not inherited from std::exception

 throw "Stack is empty. Pop failed"; 

This is a bad practice example of using a throw statement. While it can be caught in various ways like

catch(const char* e) { // handle exception std::cerr << e << std::endl; exit(1); } 

it shouldn't be done like this. You will loose any distinction about certain categories of exceptions that could occur (again: Don't reinvent the wheel. Get familiar with the C++ standard library instead).

The C++ exception hierarchy is based on std::exception, and what you actually have is a runtime failure. So you should rather use the standard exception class that indicates that:

throw std::runtime_error("Stack Class Error: Stack is empty. Pop failed"; 

The above exception could be caught transparently and reported using the what() function:

catch(const std::exception& e) { // handle exception std::cerr << e.what() << std::endl; exit(1); } 

5. Use the correct cast operations

static_cast<const char *>("5 / 5 + 3 - 6 * 2"), // why static_cast here? what is const_cast 

Your guts were right about that. At least that even doesn't need a const_cast since the character literal "5 / 5 + 3 - 6 * 2" already decays to a const char[] / const char* anyways.

Answer 2

• char top

  Any decent compiler should issue a

  warning: array subscript is of type 'char' [-Wchar-subscripts] 

  The reason is that signedness of char is implementation defined. If you happen to try your code on a platform where char is by default unsigned, the very first stack operation will access array[255].

• The responsibilities of parse_expression_using_stack and solve_expression_using_stack are badly intermingled. The parser should either interpret the input completely, or do not do any arithmetics at all.

• push into a full stack is silently ignored.