🧱 Unit 1 – Data Structures और Algorithms · Lesson 10
Infix से Postfix और Evaluation
Infix, prefix और postfix
Infix में operator operands के बीच होता है (A + B) – जैसे हम गणित लिखते हैं। Prefix (Polish) में पहले (+ A B); postfix (Reverse Polish) में बाद में (A B +)।
| Infix | Prefix | Postfix |
|---|---|---|
| A + B | + A B | A B + |
| A + B * C | + A * B C | A B C * + |
| (A + B) * C | * + A B C | A B + C * |
Postfix क्यों?
Computer stack की मदद से postfix को बाएँ से दाएँ एक ही scan में evaluate कर लेता है, न brackets चाहिए न precedence याद रखनी। Compilers और calculators अंदर ही अंदर infix को postfix में बदलते हैं।
Precedence और associativity
| Operator | Precedence | Associativity |
|---|---|---|
| ^ | सबसे ऊँची (3) | दाएँ से बाएँ |
| * / | 2 | बाएँ से दाएँ |
| + - | सबसे नीची (1) | बाएँ से दाएँ |
Conversion के नियम
- 1Operand (A, B, 5…) → postfix में लिखें
- 2'(' → stack पर push
- 3')' → '(' मिलने तक pop करके लिखें; '(' हटा दें
- 4Operator → जब तक top की precedence ज़्यादा या बराबर हो (^ छोड़कर) pop करके लिखें, फिर push करें
- 5Expression ख़त्म → बचा सब pop करके लिखें
Step-by-step trace
Python
# Trace table for converting A+B*C-D
expr = 'A+B*C-D'
prec = {'+': 1, '-': 1, '*': 2, '/': 2}
stack, out = [], ''
print('Symbol Stack Postfix')
for ch in expr:
if ch.isalpha():
out += ch
else:
while stack and prec[stack[-1]] >= prec[ch]:
out += stack.pop()
stack.append(ch)
print(ch.ljust(7), ''.join(stack).ljust(7), out)
while stack:
out += stack.pop()
print('end'.ljust(7), ''.ljust(7), out)Symbol Stack Postfix
A A
+ + A
B + AB
* +* AB
C +* ABC
- - ABC*+
D - ABC*+D
end ABC*+D-
Python: infix से postfix
Python
def precedence(op):
if op == '^':
return 3
if op in '*/':
return 2
if op in '+-':
return 1
return 0
def infix_to_postfix(expr):
stack, out = [], []
for ch in expr.replace(' ', ''):
if ch.isalnum(): # operand goes straight to output
out.append(ch)
elif ch == '(':
stack.append(ch)
elif ch == ')':
while stack[-1] != '(':
out.append(stack.pop())
stack.pop() # throw away '('
else: # operator
while (stack and stack[-1] != '(' and
(precedence(stack[-1]) > precedence(ch) or
(precedence(stack[-1]) == precedence(ch) and ch != '^'))):
out.append(stack.pop())
stack.append(ch)
while stack:
out.append(stack.pop())
return ''.join(out)
for e in ['A+B*C', '(A+B)*C', 'A*B+C/D', 'A+B*(C-D)/E', 'A^B^C']:
print(e.ljust(12), '->', infix_to_postfix(e))A+B*C -> ABC*+
(A+B)*C -> AB+C*
A*B+C/D -> AB*CD/+
A+B*(C-D)/E -> ABCD-*E/+
A^B^C -> ABC^^
Postfix evaluate करना
- 1Operand → push करें
- 2Operator → B (top) pop, फिर A pop
- 3A op B निकालकर result push करें
- 4आख़िर में बची एक value ही answer है
Python
def eval_postfix(tokens):
stack = []
for t in tokens.split():
if t.isdigit():
stack.append(int(t))
else:
b = stack.pop() # second operand (top)
a = stack.pop() # first operand
if t == '+': stack.append(a + b)
elif t == '-': stack.append(a - b)
elif t == '*': stack.append(a * b)
elif t == '/': stack.append(a / b)
print('apply', a, t, b, '-> stack', stack)
return stack.pop()
print('Result:', eval_postfix('5 6 2 + * 12 4 / -'))apply 6 + 2 -> stack [5, 8]
apply 5 * 8 -> stack [40]
apply 12 / 4 -> stack [40, 3.0]
apply 40 - 3.0 -> stack [37.0]
Result: 37.0
Practice
- (A+B)*(C-D) को postfix में बदलें। उत्तर: AB+CD-*
- 2 3 4 * + 5 - evaluate करें। उत्तर: 9
- A/B-C*D+E बदलें। उत्तर: AB/CD*-E+
अक्सर पूछे जाने वाले प्रश्न (FAQ)
Postfix notation क्या है?
Operators अपने operands के बाद लिखे जाते हैं, जैसे A+B की जगह AB+। Evaluate करने के लिए brackets या precedence नियमों की ज़रूरत नहीं।
Infix से postfix बदलने में कौन सा data structure लगता है?
Stack, जो operators और brackets को तब तक रखता है जब तक उन्हें output में न लिखा जा सके।
Postfix evaluate करते समय कौन सा operand पहले pop होता है?
दूसरा (दायाँ) operand पहले pop होता है, फिर पहला (बायाँ); - और / के लिए यह ज़रूरी है।
