Data Structures and Their Applications
Covering the fundamentals and practical applications of linear data structures such as stacks, including reversing strings, balancing symbols, postfix expression evaluation, and infix-to-postfix expression translation. Examples and algorithms explained with illustrations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Linear Data Structures Stack SACHIN KHARDE
Applications of stack Reversing the string Balancing symbols Postfix expression evaluation Translating infix expression to postfix expression SACHIN KHARDE
Reversing the string push each character on to a stack as it is read. When the line is finished, we then pop characters off the stack, and they will come off in the reverse order. SACHIN KHARDE
Reversing the string void ReverseRead(void) { //using static Stack class of Lecture#3 Stack<char> stack;//The Stack stack is created char item; cin>>item; while (!stack.isFull()&&item!='$')//type in $ from keyboard to stop input { stack.push(item); // push each character onto the stack cin>>item; } while(!stack.isEmpty() ) { item=stack.pop ();//Pop an element from stack cout<<item; } } SACHIN KHARDE
Balancing Symbols Compilers use a program that checks whether every symbol (like braces, parenthesis, brackets, etc) in a program is balanced. The simple algorithm for this purposeis: Make an empty stack. 1. Read the characters until end of file. 2. If the character is an open any thing, push it onto the stack. 3. If it is a close any thing,then 4. if the stack is empty report an error. Otherwise Pop the Stack. If the popped symbol is not the corresponding opening symbol, then report an error. At the end of the file, if the stack is not empty report an error. 5. SACHIN KHARDE
a b / c + d * e Precedence? 1. b/c 2. d*e 3.a a1 4. t2 + a2 /a1 = b/c / / t2 = a b/c / /a2 = d*e/ SACHIN KHARDE
Infix = a * b + c ((a*b) +c) Priority: 1. a * b 2. a1 + c / a1 = a * b / Prefix = * a b , +a1 c +*abc Suffix = ab* , a1c+ ab*c+ SACHIN KHARDE
infix = a- b * c / d + e / f suffix =a bc* / d + e / f a bc*d/ + e / f a bc*d/ + ef/ abc*d/- + ef/ abc*d/-ef/+ prefix =a - *bc / d + e / f a - /*bcd + e / f a - /*bcd + /ef -a/*bcd + /ef +-a/*bcd/ef SACHIN KHARDE
Infix: a+b*c d/f+e Suffix: abc*+df/-e+ Prefix: +-+a*bc/dfe SACHIN KHARDE
Postfix Expression Evaluation When a number is seen, it is pushed onto the stack When an operator is seen, then pop two elements from stack and push the result onto the stack. Now we evaluate the following postfix expression. 6 5 2 3 + 8 * + 3 +* The first four are placed on the stack. The resulting stack is 3 2 1. 5 6 stack SACHIN KHARDE
evaluating the following postfix expression. 6 5 2 3 + 8 * + 3 +* 3 2 5 6 stack 2. Next a + is read, so 3 and 2 are popped from the stack and their sum 5 is pushed. 5 5 6 stack SACHIN KHARDE
evaluating the followingpostfix expression. 6 5 2 3 + 8 * + 3 + * 5 5 6 stack 8 3. Next 8 is read andpushed. 5 5 6 stack SACHIN KHARDE
evaluating the followingpostfix expression. 6 5 2 3 + 8 * + 3 + * 8 5 5 6 stack 4. Next a * is seen so 8 and 5 are popped as 8 * 5 = 40 ispushed 40 5 6 stack SACHIN KHARDE
evaluating the followingpostfix expression. 6 5 2 3 + 8 * + 3 + * 40 5 6 stack 5. Next a + is read so 40 and 5 are popped and 40 + 5 = 45 ispushed. 45 6 stack SACHIN KHARDE
evaluating the followingpostfix expression. 6 5 2 3 + 8 * + 3 + * 45 6 stack 6. Now 3 ispushed 3 45 6 stack SACHIN KHARDE
evaluating the followingpostfix expression. 6 5 2 3 + 8 * + 3 + * 3 45 6 stack 7. Next symbol is + so pops 3 and 45 and pushes 45 + 3 = 48, so push 48 in stack. 48 6 stack SACHIN KHARDE
evaluating the followingpostfix expression. 6 5 2 3 + 8 * + 3 + * 48 6 stack 7. Finally a * is seen and 48 and 6 are popped, the result 6 * 48 = 288 is pushed. 8. As there is no input, so pop the stack and we get the result. 288 stack SACHIN KHARDE
Translating infix expressions to postfixexpression When an operand is read, it is immediately placed onto the output. When an operator or left parenthesis comes then save it in the stack initially stack is empty. If we see a right parenthesis, then we pop the stack, writing symbols until we encounter a (corresponding) left parenthesis, which is popped but not output. If we see any other symbol ( + , * , ( , etc) then we pop entries form the stack until we find an entry of lower priority. One exception is that we never remove a ( from the stack except when processing a ) . When the popping is done, we push the operand onto the stack. Finally, if we read the end of input, we pop the stack until it is empty, writing symbols onto the output. SACHIN KHARDE
Translating infix expressions to postfixexpression Convert the following infix expression to postfix expression. a+b*c+(d*e+f)*g 1. First the symbol a is read, so it is passed through to theoutput a 2. Then + is read and pushed onto thestack. output + stack 3. Next b is read and passed through to theoutput. ab * output 4. Next a * is read. The top entry on the operator stack has lower precedence than *, so nothing is output and * is put on the . + stack SACHIN KHARDE
Converting the following infix expression to postfix expression. a+b*c+(d*e+f)*g 5. Next, c is read andoutput. abc output 6. The next symbol is a +. Checking the stack, we find that priority of stack top symbol * is higher than + . So we pop a * and place it on the output, Pop the other +, which is not of lower but equal priority, and then push +. * abc*+ output + + stack stack SACHIN KHARDE
Converting the following infix expression to postfix expression. a+7.b*Tch+e(dn e*xet +s yfm)*bgo l read is an ( , which, being of highest precedence, is placed on the stack. ( + stack 8. Then d is read andoutput. abc*+d output SACHIN KHARDE
Converting the following infix expression to postfix expression. a+b*c+(d*e+f)*g 9. We continue by reading a *. Since open parenthesis do not get removed except when a closed parenthesis is being processed, there is no output and we push * instack * ( + stack 10. Next, e is read andoutput. abc*+de output SACHIN KHARDE
Converting the following infix expression to postfix expression. a+b*c+(d*e+f)*g 11. The next symbol read is a +, since priority of stack top value is higher so we pop * and push +. + abc*+de* output ( + stack 12. Now we read f and outputf. abc*+de*f output SACHIN KHARDE
Converting the following infix expression to postfix expression. a+13b.*Nc+ow(dw*eer+eaf)d*ag ) , so the stack is emptied back to the ( , we output a +. abc*+de*f+ + output stack 14. We read a * next; it is pushed onto thestack. * + stack 15. Now, g is read andoutput. abc*+de*f+g output SACHIN KHARDE
Converting the following infix expression topostfix expression. a+b*c+(d*e+f)*g * + stack 16. The input is now empty, so pop output symbols from the stack until it is empty. abc*+de*f+g*+ output stack SACHIN KHARDE
