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; }
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.
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
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:
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:
We then evaluate 7+3
and push the result to the stack. The stack becomes
Once we read the final closing bracket )
we pop everything from the stack and evaluate 10*11
.
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; }