Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit88b6caa

Browse files
ashwekpoyea
authored andcommitted
fixed balanced_parentheses, Added infix-prefix & postfix evaluation (TheAlgorithms#621)
* Create infix_to_prefix_conversion.py* Create postfix_evaluation.py* Update balanced_parentheses.py
1 parente6eb6db commit88b6caa

File tree

2 files changed

+111
-0
lines changed

2 files changed

+111
-0
lines changed
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
"""
2+
Output:
3+
4+
Enter an Infix Equation = a + b ^c
5+
Symbol | Stack | Postfix
6+
----------------------------
7+
c | | c
8+
^ | ^ | c
9+
b | ^ | cb
10+
+ | + | cb^
11+
a | + | cb^a
12+
| | cb^a+
13+
14+
a+b^c (Infix) -> +a^bc (Prefix)
15+
"""
16+
17+
definfix_2_postfix(Infix):
18+
Stack= []
19+
Postfix= []
20+
priority= {'^':3,'*':2,'/':2,'%':2,'+':1,'-':1}# Priority of each operator
21+
print_width=len(Infix)if(len(Infix)>7)else7
22+
23+
# Print table header for output
24+
print('Symbol'.center(8),'Stack'.center(print_width),'Postfix'.center(print_width),sep=" | ")
25+
print('-'*(print_width*3+7))
26+
27+
forxinInfix:
28+
if(x.isalpha()orx.isdigit()):Postfix.append(x)# if x is Alphabet / Digit, add it to Postfix
29+
elif(x=='('):Stack.append(x)# if x is "(" push to Stack
30+
elif(x==')'):# if x is ")" pop stack until "(" is encountered
31+
while(Stack[-1]!='('):
32+
Postfix.append(Stack.pop() )#Pop stack & add the content to Postfix
33+
Stack.pop()
34+
else:
35+
if(len(Stack)==0):Stack.append(x)#If stack is empty, push x to stack
36+
else:
37+
while(len(Stack)>0andpriority[x]<=priority[Stack[-1]]):# while priority of x is not greater than priority of element in the stack
38+
Postfix.append(Stack.pop() )# pop stack & add to Postfix
39+
Stack.append(x)# push x to stack
40+
41+
print(x.center(8), (''.join(Stack)).ljust(print_width), (''.join(Postfix)).ljust(print_width),sep=" | ")# Output in tabular format
42+
43+
while(len(Stack)>0):# while stack is not empty
44+
Postfix.append(Stack.pop() )# pop stack & add to Postfix
45+
print(' '.center(8), (''.join(Stack)).ljust(print_width), (''.join(Postfix)).ljust(print_width),sep=" | ")# Output in tabular format
46+
47+
return"".join(Postfix)# return Postfix as str
48+
49+
definfix_2_prefix(Infix):
50+
Infix=list(Infix[::-1])# reverse the infix equation
51+
52+
foriinrange(len(Infix)):
53+
if(Infix[i]=='('):Infix[i]=')'# change "(" to ")"
54+
elif(Infix[i]==')'):Infix[i]='('# change ")" to "("
55+
56+
return (infix_2_postfix("".join(Infix)))[::-1]# call infix_2_postfix on Infix, return reverse of Postfix
57+
58+
if__name__=="__main__":
59+
Infix=input("\nEnter an Infix Equation = ")#Input an Infix equation
60+
Infix="".join(Infix.split())#Remove spaces from the input
61+
print("\n\t",Infix,"(Infix) -> ",infix_2_prefix(Infix),"(Prefix)")
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
"""
2+
Output:
3+
4+
Enter a Postfix Equation (space separated) = 5 6 9 * +
5+
Symbol | Action | Stack
6+
-----------------------------------
7+
5 | push(5) | 5
8+
6 | push(6) | 5,6
9+
9 | push(9) | 5,6,9
10+
| pop(9) | 5,6
11+
| pop(6) | 5
12+
* | push(6*9) | 5,54
13+
| pop(54) | 5
14+
| pop(5) |
15+
+ | push(5+54) | 59
16+
17+
Result = 59
18+
"""
19+
20+
importoperatorasop
21+
22+
defSolve(Postfix):
23+
Stack= []
24+
Div=lambdax,y:int(x/y)# integer division operation
25+
Opr= {'^':op.pow,'*':op.mul,'/':Div,'+':op.add,'-':op.sub}# operators & their respective operation
26+
27+
# print table header
28+
print('Symbol'.center(8),'Action'.center(12),'Stack',sep=" | ")
29+
print('-'*(30+len(Postfix)))
30+
31+
forxinPostfix:
32+
if(x.isdigit() ):# if x in digit
33+
Stack.append(x)# append x to stack
34+
print(x.rjust(8), ('push('+x+')').ljust(12),','.join(Stack),sep=" | ")# output in tabular format
35+
else:
36+
B=Stack.pop()# pop stack
37+
print("".rjust(8), ('pop('+B+')').ljust(12),','.join(Stack),sep=" | ")# output in tabular format
38+
39+
A=Stack.pop()# pop stack
40+
print("".rjust(8), ('pop('+A+')').ljust(12),','.join(Stack),sep=" | ")# output in tabular format
41+
42+
Stack.append(str(Opr[x](int(A),int(B))) )# evaluate the 2 values poped from stack & push result to stack
43+
print(x.rjust(8), ('push('+A+x+B+')').ljust(12),','.join(Stack),sep=" | ")# output in tabular format
44+
45+
returnint(Stack[0])
46+
47+
48+
if__name__=="__main__":
49+
Postfix=input("\n\nEnter a Postfix Equation (space separated) = ").split(' ')
50+
print("\n\tResult = ",Solve(Postfix))

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp