1.Expression Evaluation
2Backtracking(game playing ,findings path ,searching)
3.Memory management,run time environment for nested language1.Expression Evaluation
Expression Evaluation को समजने के लिए किसी airthmatic expression को कांसिद्वेर करेगे |किसी expression मे logical और boolean expression को सामान प्रकार से solve किया जाता है |control structure भी complier के तरह treat होते है |
Expression Evaluation पढने का मतलब है किसी लम्बे Expression को छोटे expression मे ट्रांसफॉर्म करना है इसके अलावा NP complete problem को solve करने के लिए किया जाता है |इस problem के solution के अलावा , निन्म process को भी solve कर सकते है |
1.किसी graph को traverse करने के लिए shortest path को find करना |
2.BIN Packing
3.linear programming
Notation
किसी प्रोग्राम मे , a+b और a/b को solve करना easy होता है लेकिन a*b+c कोसोल्वे करने के लिएय precedence rules को use करना होता है |operator precedence के rules को अप्लाई करने के लिए prefix ,postfix और infix method को use किया जा सकता है |इसका expression को solve करने के लिए :-
|
INFIX
|
PREFIX
|
POSTFIX
|
|
A+B
|
+AB
|
AB+
|
|
A+B*C
|
+A*BC
|
ABC*+
|
|
40*3+6+1
|
||
|
(I+J)*(K+L)
|
*+IJ+KL
|
IJ+KL+*
|
POSTFIX TRANSFORMATION
इसकी algorithm है :-
1.किसी expression को left से right की तरह scan करेगे |
2.variable की value को स्किप करगे |
3.अगर operator आ जाता है ,तब इसे operand पर अप्लाई करेगे |
4.और operand पर operator को लगा कर आये आउटपुट को operand की जगह replace कर देगे |
5.scan जब तक होगी जब तक की एक value नहीं आ जाती है |
इस algorithm की time complxity O(n) होती है क्योकि इसमें expression के को कव्वाल एक बार स्कैन किया जाता है |
INFIX TRANSFORMATION
इस प्रोसेस मे stack को use किया जाता है |इस stack मे operator की detail को hold करता है जिसे operand को solve करने के लिए किया जाता है |इसकी algorithm है :-
1.stack को empty बनाना या empty postfix आउटपुट string
2.किसी stack को left तो right side से स्कैन करेगे |
3.अगर किसी stack मे operand है तब इसे operator string मे ट्रांसफॉर्म हो जायेगा |
4.अगर current input त्योकें operator है और operator जिसका precedence equal और higher है तो इसे आउटपुट string मे ट्रांसफॉर्म करेगे |फिर operator को stack मे push करेगे |
5.अगर current input token ‘(‘ है तब इसे stack मे push करेगे |
6.अगर current input token ‘)है तब सभी operator को टैक से निकल देगे इसे आउटपुट string मे transform कर देगे जब तक ‘)’ नहीं आ जाता है |
7.जब input string का end हो जाता है |सभी operator को stack से निकल देगे और इसे आउटपुट string मे transform कर देगे |
इस algorithm error को handel नहीं करती है इसलिए () के केयरफुल handel करना होता है |
उदहारण के लिए (A*B-(C-D))/(E+F) , इसके लिए stack और आउटपुट string की table नीचे है |
|
Input token
|
stack
|
Output string
|
|
(
|
(
|
|
|
A
|
(
|
A
|
|
*
|
(*
|
A
|
|
B
|
(*
|
AB
|
|
–
|
(-
|
AB*
|
|
(
|
(-(
|
AB*
|
|
C
|
(-(
|
AB*C
|
|
–
|
(-(-
|
AB*C
|
|
D
|
(-(-
|
AB*CD
|
|
)
|
(-
|
AB*CD-
|
|
)
|
AB*CD–
|
|
|
/
|
/
|
AB*CD–
|
|
(
|
/(
|
AB*CD–
|
|
E
|
/(
|
AB*CD–E
|
|
+
|
/(+
|
AB*CD–E
|
|
F
|
/(+
|
AB*CD–EF
|
|
)
|
/
|
AB*CD–EF+/
|
Call or Return Process :
जब किसी function / method को call किया जाता है tab
1.एक active record create हो जाता है जो local variable और parameter की size और number पर निर्भर करता है |
2.base pointer होता है जो की स्पेशल location जो की reserved होती है के address को hold करता है |
3.प्रोग्रामर counter function के return address को hold करता है |
4.base pointer नए base या stack के top से रिसेट हो जाता है |
5.और प्रोग्राम counter function / method जिसे call किया जाता है के first bytecode से set हो जाता है |
6.call function के सभी parameters को parameter region मे store कर देते है |
7.और सभी local variable ,local region मे store हो जाता है |
जब method execute होता है तब local variable और parameter को easily प्राप्त कर लेते है |इसे प्राप्त करने के लिए सभी variable से एक constant को जोड़ देते है जिसे variable को access कर लेते है इन constant को base pointer मे सेव होते है |
जब method/ function return होते है तब
1.सबसे पहले active record से program counter को call करते है और इसे pc मे change कर देते है |
2.base pointer की value को कल करते है इसे कंप्यूटर के base pointer से replace कर लेते है |
3.stack के top से नए base को pop कर लेते है |