Evaluating formulas using stack

A stack can be used to evaluate formulas with brackets and operations +, -, and * on integers. The formula must have brackets around each of the operation. For example, the formulas "8" and "(1+7)" are legal, while "1+7" is not because it has the operation + but does not have parenthesis.

The function will take a string as an input. Then we will break the string into "FormulaItems". For example, the string ((7*(18+2))+(5+2)) contains the following items:

item01: (

item02: (

item03: 7

item04: *

item05: (

item06: 18

item07: +

item08: 2

item09: )

item10: )

item11: +

item12: (

item13: 5

item14: +

item16: 2

item17: )

item18: )

Each item except for ")" is pushed to the stack. Once we arrive to the item ")", then we pop the last four items from the stack. The second (middle) one is an operation. The first and the third are the numbers. The fourth from the last must be "(". We now evaluate the formula, obtain a number, and push that number back to the stack.

This is the implementation of the algorithm in C++.

#include<iostream>
class FormulaItem{
public:
  std::string operation;
  int value;
};
class Stack{
public:
  FormulaItem x;
  Stack* next;
};
Stack* push(Stack* oH, FormulaItem input){
  Stack* nN;
  nN=new Stack;
  nN->x=input;
  nN->next=oH;
  return nN;
}
Stack* pop(Stack* oH){
  if(oH==nullptr){
    return nullptr;
  }
  Stack* nextNode;
  nextNode=oH->next;
  delete oH;
  return nextNode;
}
int isEmpty(Stack* top){
  if(top==nullptr){
    return 1;
  }
  return 0;
}

void deleteStack(Stack* top){
  while(top!=nullptr){
    top=pop(top);
  }
}
int nextInteger(const std::string &input, int &i){
  int len=input.length();
  int result=0;
  while((i<len)&&(input[i]>='0')&&(input[i]<='9') ) {
    result *= 10;
    result += static_cast<int>(input[i]-'0');
    ++i;
  }
  return result;
}
std::pair<int,int> calculate(const std::string &input){
  std::pair<int,int> error;
  std::pair<int,int> success;
  error.second=1;
  success.second=0;
  int len=input.length();
  int i=0;
  FormulaItem current, firstNum, middleOperation,secondNum,openingBracket;
  Stack* top=nullptr;
  while(i<len){
    switch(input[i]){
      case '(':
      case '+':
      case '-':
      case '*':
        current.operation=input[i];
        top=push(top,current); 
        ++i;
        break;
      case ')':
        if(top==nullptr){deleteStack(top); return error;}
        secondNum=top->x;top=pop(top);
        if((secondNum.operation!="number")||(top==nullptr)){deleteStack(top); return error;}
        middleOperation=top->x;top=pop(top);
        if(top==nullptr){deleteStack(top); return error;}
        firstNum=top->x;top=pop(top);
        if((firstNum.operation!="number")||(top==nullptr)){deleteStack(top); return error;}
        openingBracket=top->x;top=pop(top);
        if(openingBracket.operation!="("){deleteStack(top);return error;}
        current.operation="number";
        switch(middleOperation.operation[0]){
          case '+':
            current.value=firstNum.value+secondNum.value;
            break;
          case '-':
            current.value=firstNum.value-secondNum.value;
            break;
          case '*':
            current.value=firstNum.value * secondNum.value;
            break;
          default:
            deleteStack(top);
            return error;
        }
        top=push(top,current);
        ++i;
        break;
      default:
        current.operation="number";
        current.value=nextInteger(input,i);
        top=push(top,current);
    }
  }
  if(top==nullptr){deleteStack(top); return error;}
  current=top->x;
  if(current.operation!="number"){deleteStack(top);return error;}
  top=pop(top);
  if(top!=nullptr){deleteStack(top);return error;}
  success.first=current.value;
  return success;
}

int main(){
  std::string inputString;
  std::cin>>inputString;
  std::pair<int,int> res=calculate(inputString);
  if(res.second==1){
    std::cout<<"Error in formula.\n";}
  else{
    std::cout<<inputString<<" = "<<res.first<<"\n";}
  return 0;
}