Question

In c++

Section 1. Stack ADT – Overview 

Data Items

The data items in a stack are of generic DataType. This means use should use templating and your Node class.

Structure 

The stack data items are linearly ordered from the most recently added (the top) to the least recently added (the bottom). This is a LIFO scheme. Data items are inserted onto (pushed) and removed from (popped) the top of the stack. 

Operations 

Constructor. Creates an empty stack. 

Copy constructor. Initializes the stack to be equivalent to the other Stack object parameter. 

Overloaded assignment operator. Sets the stack to be equivalent to the other Stack object parameter and returns a reference to the modified stack. 

Destructor. Deallocates the memory used to store the stack. 

push (const DataType& newDataItem) 

Requirements: Stack is not full. 

Results: Inserts newDataItem onto the top of the stack. 

DataType peek()

    Requirements: Stack is not empty

Results: returns a copy of  the value of the most recently added (top) data item from the stack

void pop() 

Requirements: Stack is not empty 

Results: Removes the most recently added (top) data item from the stack. 

void clear() 

Requirements: None 

Results: Removes all the data items in the stack. 

bool isEmpty() const 

Requirements: None 

Results: Returns true if the stack is empty. Otherwise, returns false. 

bool isFull () const 

Requirements: None 

Results: Returns true if the stack is full. Otherwise, returns false. 

Section 2. Implementation Approaches

As in the class, we consider both

Array-based implementations

Linked-List implementations

For this assignment, create the link-based implementation!

Section 3. 

Programming Exercise 1

We commonly write arithmetic expressions in the so-called infix form. That is, with each

operator placed between its operand, as below

(5+6)*(4/3)

Although we are comfortable writing expressions in this form, infix form has the

disadvantage that parentheses must be used to indicate the order in which operators

are to be evaluated. These parentheses, in turn, complicate the evaluation process.

Evaluation is much easier if we can simply evaluate operators from left to right.

Unfortunately, this evaluation will not work with the infix form of arithmetic expressions.

However, it will work if the expression is in postfix form. In the postfix form of an arithmetic

expression, each operator is placed immediately after its operands. The expression

above is written in postfix form as

56+43/*

Note that both forms place the numbers in the same order (reading from left to right).

The order of the operators is different, however, because the operators in the postfix form

are positioned in the order that they are evaluated. The resulting postfix expression is hard

to read at first, but it is easy to evaluate programmatically. We will do so with stacks.

Suppose you have an arithmetic expression in postfix form that consists of a sequence of

single digit, nonnegative integers and the four basic arithmetic operators (+,-,*,/). This

expression can be evaluated using the following algorithm in conjuction with a stack of

floating-point numbers.

Read the expression character-by-character. As each character is read in:

If the character corresponds to a single digit number (characters ‘0’ to ‘9’), then

push the corresponding floating-point number onto the stack.

If the character corresponds to one of the arithmetic operators (characters ‘+’, ‘-

‘, ‘*’, ‘/’), then

Pop a number off of the stack. Call it operand1.

Pop a number off of the stack. Call it operand 2.

Combine these operands using the arithmetic operator, as follows

Result = operand2 operator operand1

Push result onto the stack.

When the end of the expression is reached, pop the remaining number off the stack. This

number is the value of the expression. Applying this algorithm to the arithmetic expression

34+52/*

Results 17.5 as expected.

Create a program that reads the infix form of an arithmetic expression, evaluates it, outputs the postfix expression, and outputs the result. Assume that the expression consists of single-digit, nonnegative integers (‘0’ to ‘9’) and the FIVE basic arithmetic operators (‘+’,’-‘,’*’,’/’,’^’) (note to correctly handle ‘^’). Further assume that the arithmetic expression is input from the keyboard with all the characters separated by white space on one line. Save your program in a file called postfix.cpp

Answer 1

#include<bits/stdc++.h>

using namespace std;

//Function to return precedence of operators

int pred(char c)

{

if(c=='^')

return 3;

else if(c=='*'||c=='/')

return 2;

else if(c=='+'||c=='-')

return 1;

else

return -1;

}

//Main function to convert infix to postfix

void infixToPostfix(string s)

{

std::stack<char>st;

st.push('N');

int l=s.length();

string ns;

for(int i=0;i<l;i++)

{

if((s[i]>='a' && s[i]<='z')||(s[i]>='A' && s[i]<='Z'))

ns+=s[i];

else if(s[i]== '(' )

st.push( '(' );

else if(s[i]== ')' )

{

while(st.top()!='N' && st.top()!= '(' )

{

char c = st.top();

st.pop();

ns +=c;

}

if(st.top() == '(' )

{

char c =st.top();

st.pop();

}

}

else{

while(st.top() !='N' && prec(s[i]) <= prec(st.top()))

{

char c = st.top();

st.pop();

ns +=c;

}

st.push(s[i]);

}

}

//pop all remaining elements from the stack

while(st.top() != 'N')

{

char c =st.top();

st.pop();

ns += c;

}

cout << ns << endl;

}

int main()

{

string exp = "a+b*(c^d-e)^(f+g*h)-i";

infixToPostfix(exp);

return 0;

}