Validator for mathematical expression in infix form

Question

This program will validate whether a mathematical expression entered by the user is a valid expression based off whether the expression itself has been entered with the correct scope openers and scope closers. The program will then send the results to a text file. The program will not compute the mathematical expression (that will come later when i have this part down)

#include<iostream>
#include<cctype>
#include<fstream>
#include<cstdlib>
#include<istream>
using namespace std;
struct NodeType;
typedef NodeType* Nodeptr;
typedef char StackType;
class Stack
{
 public:
 bool IsEmpty()const;
 bool IsFull() const;
 void Push(StackType newItem);
 StackType StackTop() const;
 void Pop();
 Stack();
 ~Stack();
 private:
 Nodeptr top;
};
struct NodeType
{
 StackType item;
 Nodeptr link;
};
// Function declarations 
void describeProgram();
void read_expression(char expression[80]);
void check_expression(char expression[80], bool& valid); 
void report_result(char expression[80], bool valid);
bool another();
int main()
{
 char expression[80]; //Expression to be read from the keyboard
 bool valid; //true id expression is valid, false otherwise 
 do
 {
 read_expression(expression);
 check_expression(expression, valid);
 report_result(expression, valid);
 }while(another());
 system("PAUSE");
 return 0;
}
Stack::Stack()
{
 top = NULL;
}
Stack::~Stack()
{
 Nodeptr p;
 while(top != NULL)
 {
 p = top;
 top = top->link;
 delete p;
 };
 cout<<"Stack has been reallocated to the heap."<<endl;
 return;
}
bool Stack::IsEmpty() const
{
 return (top == NULL);
}
bool Stack::IsFull() const
{
 int* p;
 return (!(p = new int));
}
void Stack::Push(StackType newItem)
{
 Nodeptr q;
 q = new NodeType;
 q->item = newItem;
 q->link = top;
 top = q;
 return;
}
StackType Stack::StackTop() const
{
 return top->item;
}
void Stack::Pop()
{
 Nodeptr p;
 p = top;
 top = top->link;
 delete p;
 return;
}
void describeProgram()
{ 
 cout << "This program prompts the user for a mathematical expression. After,"
 "the program will check to see whether the expression is valid or "
 "invalid. After its validity is confirmed or denied, the program will"
 " let the user know. The user will be asked if they want to repeat "
 "the program."; 
}
void read_expression(char expression[80])
{
 cout << "Enter your mathematical expression: \n";
 cin.ignore();
 cin.getline(expression, 80);
 while(expression == NULL)
 {
 cout << "Please enter a valid expression: \n";
 cin.ignore(); 
 cin.getline( expression, 80);
 }
 return;
}
void check_expression(char expression[80], bool& valid)
{
 Stack symbStack; 
 char symbol, top_symb; 
 int i = 0; 
 valid = true; 
 symbol = expression[i];
 while(symbol != '0円') 
 {
 if( symbol == '{' || symbol == '[' || symbol == '(' )
 {
 symbStack.Push(symbol);
 }
 else if( symbol == '}' || symbol == ']' || symbol == ')' )
 {
 if(symbStack.IsEmpty())
 {
 cout << "Expression is invalid! \n";
 valid = false;
 return;
 }
 else
 {
 top_symb = symbStack.StackTop();
 symbStack.Pop();
 } 
 if( (top_symb != '(' && symbol == ')') || 
 (top_symb != '[' && symbol == ']') ||
 (top_symb != '{' && symbol == '}') )
 {
 valid = false;
 }
 }
 i++; 
 symbol = expression[i]; 
 }
 if(!(symbStack.IsEmpty()))
 valid = false; 
 return; 
}
void report_result(char expression[80], bool valid)
{
 ofstream toFile;
 toFile.open("scope.txt",ios::out);
 if(!valid)
 {
 cout << "\n The expression: " << expression << " was an invalid expression \n";
 toFile << "\n The expression: " << expression << " was an invalid expression \n";
 }
 else
 {
 cout << "\n The expression: " << expression << " was a valid expression \n";
 toFile << "\n The expression: " << expression << " was a valid expression \n";
 }
 toFile.close(); 
 return;
}
bool another()
{
 char response;
 cout << "\n Do you wish to run this program again (Y or N) \n";
 cin >> response; 
 while((response!= 'N') && (response!= 'Y') && 
 (response!= 'y') && (response!= 'n'))
 {
 cout << "Please enter a valid response";
 cin >> response;
 }
 response = toupper(response);
 return response == 'Y';
}

Answer 1

Don’t write using namespace std;.

You can, however, in a CPP file (not H file), or inside a function, put individual using std::string; etc. (See SF.7.)

---

Did you know that there is a stack container adaptor in the standard library? And basing it on a linked list is slow — use a vector.

I'll note some things about the Stack code for general teaching, since you should actually not write any of that at all.

Stack::Stack()
{
 top = NULL;
}

Don’t assign values in the body of the constructor; use an initializer list. (C.49)

This one could be a default initializer (with the top field definition) and then you don’t write the constructor at all. (C.48)

But you should not have naked new (and delete). So top should actually be a unique_ptr which knows how to initialize itself so you don’t need to do anything. (R.11)

And, don’t use the C NULL macro.

---

char expression[80]; //Expression to be read from the keyboard

Don't hard-code array sizes or use them like this (R.14). The function should be written as

std::string read_expression()

---

check_expression(expression, valid);

No, return results. And declare variables where used and initialized:

bool valid = check_expression(expression);

Using "out" parameter instead of returns is bad; for no reason is just horrible. (See F.20.)

Your parameters taking arrays probably don't mean what you think. In any case, pass std:string (or string_view which can be especially handy for parsing).

---

return (top == NULL);

Don’t use the C NULL macro (ES.47). But, don’t write explicit tests against nullptr. (ES.87) Use the contextual conversion to bool, which works efficiently for raw pointers and any kind of smart pointer instance.

---

bool Stack::IsFull() const
{
 int* p;
 return (!(p = new int));
}

That makes no sence! You leak memory, and always return true since new throws an exception on failure. How can a linked list be full, anyway?

---

It’s good to use typedefs instead of the actual type, for clarity in reading the code as well as for ease in changing things.

typedef char StackType;

But, typedef is obsolete and limited. Today, write instead (T.43)

using StackType = char;

But don’t (generally) typedef pointers to other things. Read and understand something* as a pointer to something, not needing another unique name like somethingpointer instead.

---

You don’t need a return at the end of a void function.

Answer 2

I’ll go over check_expression itself, the meat of your logic, in a separate message. Your other functions are just incidental and you just need to learn what’s already in the library and the usual good practices.

Stack symbStack; 
char symbol, top_symb; 
int i = 0; 
valid = true; 
symbol = expression[i];
while(symbol != '0円') 

Good in defining symbStack inside the function (not as a global).

You should define symbol at first use and initialize it; and having top_symb (needs to be remembered across loop iterations) is awkward.

---

Your loop is awkward, in that symbol and i=0 is set before beginning the loop, and updated at the end. This should really be a for loop, and symbol moved inside:

const auto max = strlen(expression);
for (i=0; i < max; ++i) {
 auto symbol= expression[i];
 ⋮

But really, don’t iterate using i index! You really want the symbol and don’t care about i at all. So write^※(注記):

for (auto symbol : expression) {
 ⋮

and that’s so much clearer and direct!

Back to dealing with top_symb — instead of remembering it between loop iterations, record what you pop off the stack, and only pop when you detect a closing-type symbol, so you know it must in fact be popped. It will either match, or signal an error so you don’t care anymore.

---

It would be handy to have a simple function to classify characters as opening, closing, or not interesting.

Also, move the matching of the proper open-close pair to another helper function.

Here is my rewrite:

bool check_expression (string_view s)
{
 std::stack <Symbol_type, std::vector<Symbol_type>> openstack;
 for (auto const ch : s) {
 switch (classify(ch)) {
 case boring: break;
 case open_delim:
 openstack.push(ch);
 break;
 case close_delim:
 if (openstack.empty()) return false; // close with no opens
 if (openstack.top() != match_for(ch)) return false; // wrong kind of close
 openstack.pop();
 break;
 }
 }
 return openstack.empty();
}

Even without seeing the various helpers it calls, you should understand it. Writing this first and then getting those helpers to work as smaller problems is Top-Down Design.

Here is the whole program which you can save, compile, and run.

The stuff at the beginning of the file:

#include <string>
#include <iostream>
#include <string_view>
#include <vector>
#include <stack>
using std::string_view;
using Symbol_type = char; // abstract this out to make it easy to change it to Unicode
 // and more easily illustrate in the code where variables are being used for this purpose.

Now I define my matches.

// Use tables of data and a loop, not repeated code with slightly different names each time.
// this also makes it easy to *extend*, and it is clear that the logic for matching open/close
// is right since it’s in one place.
constexpr std::pair<Symbol_type,Symbol_type> matchers[] = {
 {'(',')'}, {'[',']'}, {'{','}'}
};

Note that each symbol is only typed once, and the way they pair up is listed in the data. Suppose the next order is to have a version that includes angle brackets as delimiters — just update the table; no code to change at all. Making it have different modes that are selected with a parameter would only be a little more work (throwing everything in a class and making the table a class member).

Now the helpers themselves, that use this data to know what to do:

// simple functions that use this chart to know the results
enum charkind { boring, open_delim, close_delim };
charkind classify (Symbol_type c)
{
 for (auto [left,right] : matchers) {
 if (c == left) return open_delim;
 if (c == right) return close_delim;
 }
 return boring;
}
Symbol_type match_for (Symbol_type c)
{
 // too much trouble to set up std::find ... a for loop is so easy,
 // and can start by copying the previous function and just change the return values!
 for (auto [left,right] : matchers) {
 if (c == left) return right;
 if (c == right) return left;
 }
 throw std::invalid_argument(__FUNCTION__);
}

So simple! It doesn’t matter how many sets of different delimiters we define, the code is only doing the test once, in general. There can only be three cases: the passed-in symbol matches the left, matches the right, or does not match anything. So, the function is only 4 lines long including a line for the loop.

The check_expression function is next in the file, and you already saw that. I define the functions in order of dependency, so there are no forwarding declarations. So, main is at the bottom, the simplest helpers at the top.

I finish off the file with some testing. I did not prompt the user for input or whether he wants to run it again; just called the function a number of times with some test cases. In "real life" this is the way it works: you have unit tests that can be run automatically and contain carefully considered cases to check for.

The programmer who ordered this function might end up using it wherever, so it does not deal with input or output: it is given parameters and returns results. For example, it may be used in a form validator, not a console program.

void test (int id, string_view s)
{
 bool OK = check_expression (s);
 std::cout << id << " - " << std::boolalpha << OK << '\n';
}
int main()
{
 test (1, R"Q(constexpr std::pair<Symbol_type,Symbol_type> matchers[] = {
 {'{',')'}, {'[',']'}, {'{','}'}
 };
 )Q");
 test (2, "testing.");
 test (3, "[ / {{{ } ");
 test (4, "this) is an empty (stack)");
}

Et Voilà!

---

Notes

※(注記) for (auto symbol : expression) assumes that expression has been changed to a string, string_view, or somesuch. As originally written, the parameter (written as an array but really a pointer) will not work, but boost::as_literal(s) will turn a nul-terminated C string into a range.

• papagaga: is () a valid expression?
• JDługosz: @papagaga it is according to his specs.

Answer 3

• Some inconsistencies with your indentation which should be fixed.

• Don't use using namespace std

• Prefer prefix over postfix

• The NodeType struct can be part of the stack.

• Using a fixed-length expression limit is asking for trouble. (Enter something longer than 80 characters and see what happens)

• system("PAUSE") is not supported on all platforms.

• You have a function that returns bool, takes it by reference and another one takes it by value. This makes for a confusing interface. On first glance people might think you forgot to pass it by reference in the second function.

• return at the end of a void function is not needed.

• return 0 at the end of main is redundant

• The use of raw pointers is discouraged. You should try to use smart pointers whenever possible.

• I'm confused by the IsFull() method. As of now it's never called. It just checks if you can allocate memory (presumably checking if there is any free memory left). Also what happens if it succeeds? When do you relase the memory? If you're concerned about memory then the check should be done when you allocate a new node.

Answer 4

Tokenizer, lexer, parser...

NB: There are already three good reviews of your code, so I will only comment on the broader view.

The program will not compute the mathematical expression (that will come later when i have this part down)

I'm not sure you're doing it in the right order. When you think of it, there are a lot of common parts in validating an expression and computing its result. For instance, you need first to make "words" out of a stream of characters, like integers, operators, delimiters, etc. Those words are generally called tokens, and the tool for doing it a tokenizer*. A simple example:

tokenize("(12+3.14)") => ["(", "12", "+", "3.14", ")"];

You'll also need to add meaning to the tokens. "3.14" isn't a floating point number, nor ")" a closing parenthesis -matching opening and closing symbols isn't possible until that meaning is assigned to certain symbols. Symbols tagged with their category are called lexemes, and categorizing the tokens is the job of the lexer:

lex {"(", "12", "+", "3.14", ")"}) => [ {"(", OP}, {"12", INT}, ... , ")", CP}]

You'll then need to organize the lexemes, be it to validate the expression or evaluate it. It means you need to divide the expression in sub-expressions, and decide on an order of evaluation / validation. The fact that you evaluate separately a sub-expression between parenthesis and the fact that an closing parenthesis must match an opening one are linked. The organization of the lexemes is the task of the parser:

parse ({ {"(", OP}, {"1", INT}, {"+", ADD}, {"1", INT}, {")", CP}, {"*", MUL}, {"3", INT} }
=> [*]
 | |
 [+] [3]
 | |
 [1] [1]

Is all that necessary?

Is it really necessary to distinct those three steps? Well, it isn't necessary to translate them into separate steps in your code for the simplest cases; the first two steps are frequently combined. But you have to keep them in mind, because they'll help you organize your code way better. Your current distinction between validating and evaluating is artificial. You'll go through the same steps -tokenizing, lexing, parsing- for both.

A quick and dirty example

Here's a quick attempt at a mathematical expression evaluator, which separates lexing (no need to differentiate lexing and tokenizing in this instance) and parsing which have both responsibilities for validating and evaluating in their respective perimeters: https://wandbox.org/permlink/nOz5wJ0IL8nHYMp3

*the terminology varies: tokenizer vs scanner, lexer vs tokenizer, etc.