C++ Data structure and Algorithm

Question

Analyse the stack algorithm as in Figure 1 and apply the algorithm to convert the following

infix expression to postfix form. Show the status of input, stack and output at each step of

the conversion process.

a. X + Y / Z

b. (X + Y) / Z

1. Create one empty stack.

2. While not met the ending statement

a. Read token

b. If token is:

i. ( -> push into stack

ii. ) -> pop and display the element of stack until

find bracket ‘(‘.

*Note: error occur if ‘(‘ not found

iii. Operator

1. If stack is empty or have token with higher

precedence from the stack top -> push token into

stack.

2. Else pop and display top, then repeat ->

compare new token with the new top.

iv. Operand

1. Display.

3. When the end statement is found, pop and display stack

item until stack is empty.

Figure 1: Algorithm to Convert Infix to Postfix Using Stack

Question 2:

There is a simple encryption scheme that is called “Caesar Cipher”. In a “Caesar Cipher”, the

letters in a message are replaced by the letters of a “shifted” alphabet. A “Caesar Cipher”

encodes a message by shifting each letter in a message by a constant amount of k. If k is 5, A

becomes F, B becomes G, C becomes H and so on.

Let's use Queue to encode and decode the encrypt message. Set k as -5 and decipher the

following codes by using Linear Queue.

Encrypt message: H T S L W F Y Z Q F Y N T S X

NOTE: Assume the following functions have been implemented in the Queue class. You

may USE or CALL any of these functions.

 void Enqueue(char kod);

 void Dequeue();

 char QueueFront();

 char QueueRear();

 bool Empty();

 bool Full();

a. Write the code snippet for main() function to decode the encrypt message. Then, insert

the decoded message into the Queue and display the message from the Queue.

The encrypt message is stored as the following:-

char code[16] = "HTSLWFYZQFYNTSX";

b. State the result of your output.

Answer 1

#include<iostream>

#include<stack>

#include<locale> //for function isalnum()

using namespace std;

int preced(char ch) {

if(ch == '+' || ch == '-') {

return 1; //Precedence of + or - is 1

}else if(ch == '*' || ch == '/') {

return 2; //Precedence of * or / is 2

}else if(ch == '^') {

return 3; //Precedence of ^ is 3

}else {

return 0;

}

}

string inToPost(string infix ) {

stack<char> stk;

stk.push('#'); //add some extra character to avoid underflow

string postfix = ""; //initially the postfix string is empty

string::iterator it;

for(it = infix.begin(); it!=infix.end(); it++) {

if(isalnum(char(*it)))

postfix += *it; //add to postfix when character is letter or number

else if(*it == '(')

stk.push('(');

else if(*it == '^')

stk.push('^');

else if(*it == ')') {

while(stk.top() != '#' && stk.top() != '(') {

postfix += stk.top(); //store and pop until ( has found

stk.pop();

}

stk.pop(); //remove the '(' from stack

}else {

if(preced(*it) > preced(stk.top()))

stk.push(*it); //push if precedence is high

else {

while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {

postfix += stk.top(); //store and pop until higher precedence is found

stk.pop();

}

stk.push(*it);

}

}

}

while(stk.top() != '#') {

postfix += stk.top(); //store and pop until stack is not empty.

stk.pop();

}

return postfix;

}

int main() {

string infix = "x^y/(5*z)+2";

//string infix = "(x+y)/z";

//string infix = "x+y/z";

cout << "Postfix Form Is: " << inToPost(infix) << endl;

}