6. Stacks

1. Definition and implementation

The main element of stack is its node. The node has two components: content and pointer aNext that contains an address of another node. We will use the terminology old nodes for the nodes that are added before. The youngest node is the one that is added the last. We will only keep track of the youngest node. The youngest node contains the address of the second youngest, and the second youngest node contains the address of the third youngest. The oldest node contains the nullpointer.

The procedure of adding a new node to the stack is called push. The youngest node is also called top of the stack. As mentioned earlier, it is sufficient to only keep track of the pointer to this top node. We will call this pointer aTop. Removing the top node is easy. We first save the address from aTop->aNext as this will be the new top (or youngest) node of the stack. Then we delete the top node, and update the pointer aTop to contain the address of the new youngest node.

The implementation of the stack of doubles is given below. The implementation also contains the function copyStack that creates a brand new stack with the same contents as the old one.

struct SN{// Stack Node
 double content;
 SN* aNext;
};
SN* push(SN* oldTop, double x){
 SN* nTop;
 nTop=new SN;
 nTop->content=x;
 nTop->aNext=oldTop;
 return nTop;
}
SN* pop(SN* oldTop){
 if(oldTop==nullptr){ return nullptr; }
 SN* nextNode;
 nextNode=oldTop->aNext;
 delete oldTop;
 return nextNode;
}
double readTop(SN* aTop){
 if(aTop==nullptr){ return 0.0; }
 return aTop->content;
}
int isEmpty(SN* aTop){
 if(aTop==nullptr){ return 1; }
 return 0;
}
void deleteStack(SN* aTop){
 while(aTop!=nullptr){
    aTop=pop(aTop);
 }
}
SN* copyStack(SN* aTop){
 if(aTop==nullptr){return nullptr;}
 SN* nTop=new SN;
 nTop->content=aTop->content;
 nTop->aNext=copyStack(aTop->aNext);
 return nTop;
}
void printStack(SN* aTop){
  if(aTop!=nullptr){
    printStack(aTop->aNext);
    std::cout << aTop->content<<" ";
  }
}
int main(){
  SN* aTop=nullptr;
  aTop=push(aTop,25);
  aTop=push(aTop,21);
  aTop=push(aTop,33);
  std::cout << "Created stack 1\n";
  SN* aTop2=copyStack(aTop);
  std::cout << "Created stack 2\n";
  aTop=pop(aTop);
  aTop=push(aTop,35);
  aTop=push(aTop,27);
  aTop2=push(aTop2,77);
  aTop2=push(aTop2,372);
  printStack(aTop);std::cout << "\n\n\n";
  printStack(aTop2);std::cout << "\n\n\n";
  return 0;
}
Problem 1. The user input consists of positive and negative integers. When the user inserts the integer \(0\), the input is over. The program should read the numbers from the input and print the sequence of integers that is formed according to the following rules:
  • Every positive integer is added to the end of the sequence.
  • For every negative integer \(x\) given by the user, nothing is added to the sequence. Instead, the number \((-x)\) is calculated, and the newest \((-x)\) terms are removed from the sequence.

2. Implementation of calculator

Stacks can be used to create a program that evaluates mathematical expressions. The program will calculate results of simple mathematical expressions that involve real numbers of type double. This is one example of an input that our program will process.

\begin{eqnarray*} &&((72+29)/(7-2)+(2.8*(12-7)) \end{eqnarray*}

2.1. Input values

The inputs of our program will be of type std::string. In order to highlight the importance of stacks, our program will not have all the advanced features of a typical math software. For example, our program will not be able to figure out the priorities of operations. The program will require brackets to be used around every binary operation. Hence, these will be valid inputs:

Valid inputs:
9+(2*3)
9+(2+3)
(9+2)+3

Our program will not be required to evaluate the inputs of the form:

Invalid inputs:
9+2*3
(9+2+3)*10

2.2. Main idea

The fundamental operations +, -, *, and / are always performed on two numbers. These operations are called binary operations.

The brackets will tell us the order in which the operations should be performed. The numbers, operations, and brackets will be called math elements. These math elements will be pushed onto the stack. Whenever we read the symbol ), then we start taking elements from the stack until we find the matching bracket (.

Assume that we need to calculate (11*(3+7)). Our program will first read ( and push it to the stack. Then, it will identify the number 11 and push it on top of the stack. It will keep adding the elements until the first bracket ) is reached. At that point the stack will look like this:

\begin{eqnarray*}\mbox{stack}= \begin{array}{|c|}\hline 7\\ \hline +\\ \hline 3\\ \hline (\\ \hline *\\ \hline 11\\ \hline (\\ \hline\end{array}\end{eqnarray*}

Once we read the closing bracket, then we pop the elements until we reach the opening bracket (. The two numbers will be called num1 and num2. The operations that need to be applied to them will be called operation. The stack will get smaller because elements from the stack were popped and placed into num1, num2, and operation. The memory diagram will be:

\begin{eqnarray*} \mbox{num2}=7,\; \mbox{operation}=+,\; \mbox{num1}=3,\; \mbox{stack}= \begin{array}{|c|} \hline *\\ \hline 11\\ \hline (\\ \hline\end{array}\end{eqnarray*}

We then evaluate 7+3 and push the result to the stack. The stack becomes

\begin{eqnarray*} \mbox{stack}= \begin{array}{|c|} \hline 10\\ \hline *\\ \hline 11\\ \hline (\\ \hline\end{array}\end{eqnarray*}

Once we read the final closing bracket ) we pop everything from the stack and evaluate 10*11.

2.3. Technical difficulties

Although the idea is quite simple, the final program will be a bit lengthy. We need to read elements from the string. The single input string contains numerical values, mathematical operations, and brackets.

We will create a structure called MathElement that will be capable of representing each component of math expression.

struct MathElement{
public:
  std::string info;
  double value;
  MathElement(double = 0.0);
};

The field info can be one of the following strings: +, -, *, /, (, ), number, or it can be

Error: [some explanation of an error]

The errors will contain some more specific information on why user input was not a valid mathematical formula. Also, if we identify a division by 0, we will use this filed info to place an appropriate error message.

Our code must also have a function that reads digits from the string and constructs real numbers from these digits. The entire code is given below

#include<iostream> 
struct MathElement{
public:
  std::string info;
  double value;
  MathElement(double = 0.0);
};
MathElement::MathElement(double _v){
  info="number";
  value=_v;
}
struct SN{// Stack Node
public:
 MathElement content;
 SN* aNext;
};
SN* push(SN* oldTop, MathElement x){
 SN* nTop;
 nTop=new SN;
 nTop->content=x;
 nTop->aNext=oldTop;
 return nTop;
}
SN* pop(SN* oldTop){
 if(oldTop==nullptr){ return nullptr; }
 SN* nextNode;
 nextNode=oldTop->aNext;
 delete oldTop;
 return nextNode;
}
MathElement readTop(SN* aTop){
  MathElement defaultValue;
  if(aTop==nullptr){return defaultValue; }
  return aTop->content;
}
int isEmpty(SN* aTop){
 if(aTop==nullptr){ return 1; }
 return 0;
}
void deleteStack(SN* aTop){
 while(aTop!=nullptr){
    aTop=pop(aTop);
 }
}
MathElement readNumericalValue(std::string in, long* start){
  MathElement result;
  result.info="Error: not a numerical value";
  long len=in.length();
  double beforeDecimalPoint=0.0;
  double afterDecimalPoint=0.0;
  double sign=1.0;
  long i=*start;
  while((i<len) && ((in[i]=='+')||(in[i]=='-')) ){
    if(in[i]=='-'){
      sign*=-1.0;
    }
    ++i;
  }
  while((i<len)&&(in[i]>='0')&&(in[i]<='9')){
    result.info="number";
    beforeDecimalPoint *= 10.0;
    beforeDecimalPoint+= static_cast<double>(in[i]-'0');
    ++i;
  }
  if( (i<len) && in[i]=='.'){
    ++i;
    double multiplier=0.1;
    while((i<len)&& ((in[i]>='0')&&(in[i]<='9')) ){
      result.info="number";
      afterDecimalPoint += multiplier * static_cast<double>(in[i]-'0');
      multiplier*=0.1;
      ++i;
    }
  }
  *start=i;
  result.value=sign*(beforeDecimalPoint+afterDecimalPoint);
  return result;
}
int numberTooSmall(double z){
  if( (z>-0.00000001) && (z<0.00000001) ){
    return 1;
  }
  return 0;
}
MathElement simpleCalculation(MathElement num1, 
                    MathElement operation, MathElement num2){
  MathElement result;
  if( (num1.info!="number")||(num2.info!="number")){
    result.info="Error: Unexpected input.";
    return result;
  }
  if(operation.info=="+"){
    result.value=num1.value+num2.value;
    return result;
  }
  if(operation.info=="-"){
    result.value=num1.value-num2.value;
    return result;
  }
  if(operation.info=="*"){
    result.value=num1.value*num2.value;
    return result;
  }
  if(operation.info=="/"){
    if(numberTooSmall(num2.value)){
      result.info="Error: Division by 0.";
      return result;
    }
    result.value=num1.value/num2.value;
    return result;
  }
  result.info="Error: Operation not recognized.";
  return result;
}
std::string closingBracketError(long pos){
  return "Error: Unexpected closing bracket at position "+std::to_string(pos);
}
std::string numericalValueError(MathElement m, long pos){
  std::string err="Error. Expected a numerical value instead of (";
  err+=m.info+","+std::to_string(m.value)+")";
  err+=" at position " +std::to_string(pos);
  return err;
}
std::string badCalculation(MathElement num1, 
                    MathElement operation, MathElement num2, 
                    MathElement intermediateResult, long pos){
  std::string err="Error: Could not calculate intermediate result.\n";
  err+="Failed calculation of "+std::to_string(num1.value)+operation.info;
  err+=std::to_string(num2.value)+".\n";
  err+="Message: "+intermediateResult.info+"\n";
  err+="Error happened before the position "+std::to_string(pos);
  return err;
}
MathElement evaluate(std::string input){
  SN* aTop=nullptr;
  long i=0;
  long len=input.length();
  MathElement nextEl, num1,num2,operation, intermediateResult;
  MathElement result; int expectOperation=0;
  while(i<len){
    if(input[i]=='('){
      nextEl.info="(";
      aTop=push(aTop,nextEl);
      ++i;
    }
    else{
      if(input[i]==')'){
        if(aTop==nullptr){
          result.info=closingBracketError(i+1);
          return result;
        }
        num2=readTop(aTop); aTop=pop(aTop);
        if(aTop==nullptr){
          result.info=closingBracketError(i+1);
          return result;
        }
        if(num2.info!="number"){
          result.info=numericalValueError(num2,i+1);
          deleteStack(aTop); return result;
        }
        operation=readTop(aTop); aTop=pop(aTop);
        if(operation.info=="("){
          aTop=push(aTop,num2);
        }
        else{
          if(aTop==nullptr){
            result.info=closingBracketError(i+1);
            return result;
          }
          num1=readTop(aTop); aTop=pop(aTop);
          if(aTop==nullptr){
            result.info=closingBracketError(i+1);
            return result;
          }
          if(num1.info!="number"){
            result.info=numericalValueError(num1,i+1);
            deleteStack(aTop); return result;
          }
          intermediateResult=simpleCalculation(num1,operation,num2);
          if(intermediateResult.info[0]=='E'){
            result.info=badCalculation(num1,operation,
                        num2,intermediateResult, i+1);
            deleteStack(aTop); return result;
          }
          operation=readTop(aTop); aTop=pop(aTop);
          if(operation.info!="("){
            result.info=closingBracketError(i+1);
            deleteStack(aTop);return result;
          }
          aTop=push(aTop,intermediateResult);
        }
        ++i;
      }
      else{
        if(expectOperation){
          if(input[i]!=')'){
            operation.info="";
            operation.info+=input[i];
            aTop=push(aTop,operation);
            ++i;
          }
          expectOperation=0;
        }
        else{
          num1=readNumericalValue(input,&i);
          if(num1.info!="number"){
            deleteStack(aTop);return num1;
          }
          aTop=push(aTop,num1);
          expectOperation=1;
        }
      }
    }
  }
  if(aTop!=nullptr){
    result=readTop(aTop); aTop=pop(aTop);
    if(result.info!="number"){
      deleteStack(aTop);return result;
    }
  }
  if(aTop!=nullptr){
    operation=readTop(aTop);aTop=pop(aTop);
    if(aTop==nullptr){
      result.info="Error: Input cannot be processed.";
      result.info+=" First element in the operation is missing.";
      deleteStack(aTop); return result;
    }
    num1=readTop(aTop);aTop=pop(aTop);
    if(num1.info!="number"){
      deleteStack(aTop);return num1;
    }
    result=simpleCalculation(num1,operation,result);
    if(result.info[0]=='E'){
      result.info=badCalculation(num1,operation,num2,result, 0);
      deleteStack(aTop); return result;
    }
  }
  return result;
}
int main11(){
  std::string s;
  std::cin>>s;
  long pos=0;
  MathElement nV=readNumericalValue(s,&pos);
  std::cout<<nV.info<<" "<<nV.value<<" "<<pos<<"\n";
  return 0;
}
int main(){
  std::string s;
  std::cin>>s;
  MathElement res=evaluate(s);
  if(res.info!="number"){
    std::cout<<res.info<<"\n";
  }
  else{
    std::cout<<res.value<<"\n";
  }
  return 0;
}