[go: up one dir, main page]
Scribd
Upload
11 views16 pages

DSA Stacks

The document discusses linear data structures, specifically focusing on arrays and stacks, and introduces Polish notation for expressions. It explains the three forms of expressions: infix (operators between operands), prefix (operators before operands), and postfix (operators after operands), along with rules for converting infix notation to postfix and prefix. Key operations and their precedence are also outlined, including addition, subtraction, multiplication, division, and exponentiation.

Uploaded by

lathasreeponnada
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views16 pages

DSA Stacks

The document discusses linear data structures, specifically focusing on arrays and stacks, and introduces Polish notation for expressions. It explains the three forms of expressions: infix (operators between operands), prefix (operators before operands), and postfix (operators after operands), along with rules for converting infix notation to postfix and prefix. Key operations and their precedence are also outlined, including addition, subtraction, multiplication, division, and exponentiation.

Uploaded by

lathasreeponnada
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

Data Structures

Linear Data Structure | Array


Linear Data Structure| Stack
Infix, Prefix and Postfix Forms of Expressions
Polish Notation:

 One of the major uses of stack is a Polish notation or Polish expression.


 The process of writing the operations of an expression either before their
operands or after operands are called the Polish Notation.
 The polish notation are classified into three categories:
a) Infix
b) Prefix
c) Postfix
a) Infix:
o When the operators exist between two operands then the expression is
called Infix Expression.
o Consider the sum of A and B, we apply operator “+” between two operands
and write the expression sum as A+B.
o This expression is called Infix Expression.
b) Prefix:
o When the operator is written before their operand then the resulting expression is
called Prefix Expression.
o The operator precedes the two operands, +AB are prefix polish notation of sum.
c) Postfix:
o When an operator comes after their operands the resulting expression is called
postfix expression.
o It is also called reverse Polish Notation.
o The operator follows the two operands, AB+ is called postfix or reverse polish
notation.
 Rules for converting Infix Notation to the postfix / prefix notation:
1) The operation with highest precedence is converted first and then after a
portion of the expression has been converted to postfix.
2) It is to be treated as single operand.
3) We consider five binary operation, such are (+) addition, subtraction (-),
multiplication (*), division(/) and exponentiation.
 The first four are available in C/C++, the fifth exponentiation will be
represented by the operator $ or .
 The value of expression A$B or A B is A raise to B power, for example 3 2 = 9.
4) Take only two operands at a time to convert in a postfix from like A + B AB+
5) Always convert the parenthesis first.
6) Convert postfix exponentiation second if there are more than one exponentiation
in sequence then take order from right to left.
7) Convert in to postfix as multiplication and division operator, left to right.
8) Convert in postfix as addition and subtraction left to right.

You might also like