infix kifejezés
a+b
ab+
+ab
Készítette: Szabóné Nacsa Rozália
[email protected] 1
postfix kifejezés
a+b
ab+
2
prefix kifejezés
+ab
a+b
3
ab+
+ab
4
1
Példa:
Lengyelforma J. Lukasewitz lengyel matematikus használta el ször.
ab+
(a+b)*(c-d)
infix kifejezés
+ab ab+cd-*
postfix kifejezés
postfix kifejezés
prefix kifejezés 6
infix forma:
5
El ny:
(a+b)*(c-d)
El ny:
A m veleti jelek olyan sorrendben követik egymást, amilyen sorrendben végre kell hajtani azokat.
A m veleti jel (operátor) közvetlenül az operandus(ok) után áll.
2
Lengyelforma
Infix forma
a b
ab+cd-*
+
c
d
-
op1
op2
m v
(a+b)*(c-d)
op1 3
2
1
2
m v
3
1
op2
*
1
op1
7
op2
m v
8
2
x:
Feladat: Feladat: A A standard standard bemeneten bemeneten megadott, megadott, pontosveszz pontosveszz vel lezárt, szintaktikusan helyes, infix aritmetikai kifejezést kifejezést alakítsunk át postfix kifejezésre (lengyelformára).
(
1
+
2
)
*
(
3
-
4
)
sorozat
y: sorozat
Példa:
s:
(1+2)*(3-4)
12+34-*
verem
Az Azátalakításhoz átalakításhozkét kétsorozatot, sorozatot, és ésegy egyvermet vermethasználunk. használunk. 9
x:
(
1
+
2
)
*
(
3
-
4
)
10
x:
(
1
+
2
)
*
(
3
-
4
)
sorozat
y:
y:
sorozat
s:
s:
(
verem
verem Az x sorozatot balról jobbra haladva dolgozzuk fel. A sorozat végét ; jelzi.
AAkövetkez következ szimbólum szimbólumnyitózárójel. nyitózárójel. Tegyük Tegyükaaverembe! verembe! 11
12
3
x:
(
x:
(
y:
1
y:
1
s:
(
s:
(
1
+
2
)
*
(
3
-
4
)
1
+
2
)
*
(
3
-
4
AAkövetkez következ szimbólum szimbólumoperátor. operátor. 1.1.Legfeljebb azoperátornál operátornálkisebb kisebb Legfeljebbaanyitózárójelig nyitózárójeligkivesszük kivesszükaaveremb veremb llaz prioritású operátorokat és prioritású operátorokat éskiírjuk kiírjukazokat, azokat,… …
AAkövetkez következ szimbólum szimbólumoperandus. operandus. Írjuk Írjukki! ki! 13
x:
(
y:
1
s:
(
1
+
2
)
*
(
)
3
-
4
)
+
AAkövetkez következ szimbólum szimbólumoperátor. operátor. 1.1.Legfeljebb azoperátornál operátornálkisebb kisebb Legfeljebbaanyitózárójelig nyitózárójeligkivesszük kivesszükaaveremb veremb llaz prioritású prioritásúoperátorokat, operátorokat,és éskiírjuk kiírjukazokat, azokat,majd majd 2.2.ezt eztaz azoperátort operátortbetesszük betesszükaaverembe. verembe.
14
x:
(
1
y:
1
2
s:
(
+
+
2
)
*
(
3
-
4
)
A következ következ szimbólum szimbólum operandus. Írjuk ki!
15
16
4
x:
(
1
+
y:
1
2
+
s:
(
+
2
)
*
(
3
-
4
)
x:
(
1
+
y:
1
2
+
s:
(
2
)
*
(
3
-
4
A következ szimbólum csukózárójel: 1. Írjuk ki a verem tetején lév elemeket egészen a nyitózárójelig, majd 2. vegyük ki a verem tetejér l a nyitózárójelet.
AAkövetkez következ szimbólum szimbólumcsukózárójel. csukózárójel. 1.1.Írjuk elemeketegészen egészenaa Írjukkikiaaverem veremtetején tetejénlév lév elemeket nyitózárójelig, nyitózárójelig,. .. .. . 17
x:
(
1
+
y:
1
2
+
2
)
*
(
3
)
-
4
)
s:
A következ szimbólum operátor: 1. Legfeljebb a nyitózárójelig kivesszük a veremb l az operandusnál kisebb prioritású operandusokat, és kiírjuk azokat, . . . 19
18
x:
(
1
+
y:
1
2
+
s:
*
2
)
*
(
3
-
4
)
A következ szimbólum operátor: 1. Legfeljebb a nyitózárójelig kivesszük a veremb l az operandusnál kisebb prioritású operandusokat, és kiírjuk azokat, majd 2. Ezt az operandust betesszük a verembe. 20
5
x:
(
1
+
y:
1
2
+
s:
*
(
2
)
*
(
3
-
4
)
x:
(
1
+
2
y:
1
2
+
3
s:
*
(
AAkövetkez következ szimbólum szimbólumnyitózárójel. nyitózárójel. Tegyük Tegyükaaverembe! verembe!
)
*
(
3
-
4
A következ következ szimbólum operandus. operandus. Írjuk ki!
21
x:
(
1
+
2
y:
1
2
+
3
s:
*
(
)
*
)
(
3
-
4
)
22
x:
(
1
+
2
y:
1
2
+
3
s:
*
(
-
)
*
(
3
-
4
)
A A következ következ szimbólum operátor: 1. Legfeljebb a nyitózárójelig kivesszük a veremb l az operátornál kisebb kisebb prioritású operátorokat, és kiírjuk kiírjuk azokat, majd 2. 2. ezt ezt az az operátort operátort betesszük betesszük aa verembe. verembe.
A következ szimbólum operátor. 1. Legfeljebb a nyitózárójelig kivesszük a veremb l az az operátornál kisebb prioritású operátorokat, és kiírjuk kiírjuk azokat, azokat, .. .. ..
23
24
6
x:
(
1
+
2
)
y:
1
2
+
3
4
s:
*
(
-
*
(
3
-
4
)
x:
(
1
+
2
)
*
y:
1
2
+
3
4
-
s:
*
(
-
(
3
-
4
A következ szimbólum csukózáróje. 1. Írjuk ki a verem tetején lév elemeket egészen a nyitózárójelig, . . .
A következ szimbólum operandus. Írjuk ki!
25
x:
(
1
+
2
)
*
y:
1
2
+
3
4
-
s:
*
(
)
(
3
-
4
)
A következ szimbólum csukózárójel: 1. Írjuk ki a verem tetején lév elemeket egészen a nyitózárójelig, majd 2. vegyük ki a verem tetejér l a nyitózárójelet.
26
x:
(
1
+
2
)
*
(
y:
1
2
+
3
4
-
*
s:
*
3
-
4
)
;
Elértük a kifejezés végét. Írjuk ki a veremben lév összes elemet.
27
28
7
Feladat: Feladat: Határozzuk Határozzuk meg meg egy egy sorozatban sorozatban elhelyezett, elhelyezett, postfix postfix (lengyelformára (lengyelformára hozott) hozott) kifejezs kifejezs értékét. értékét.
y:
1
v:
1
2
+
3
4
-
* verem
példa A A szimbólum szimbólum operandus. Tegyük a verembe!
-3
12+34-*
29
y:
1
2
v:
1
2
+
3
4
-
30
y:
*
1
2
+
3
4
-
*
2
verem
v:
1
verem
A A következ következ szimbólum szimbólum operandus. Tegyük a verembe!
A következ szimbólum operator. 1. Vegyük ki a veremb l a második operandust, . . .
31
32
8
y:
1
2
+
3
1
4
-
y:
*
1
2
2
+
3
1
v:
4
-
2
* 3
v:
verem
A következ szimbólum operator: 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, majd 3. Számítsuk ki az adott m veleti jellel a kifejezés értékét, . . .
A következ szimbólum operator: 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, . . .
verem
33
y:
1
2
+
3
1
v:
4 2
-
*
y:
1
2
v:
3
3
+
3
4
-
*
3
verem
3
34
A következ szimbólum operator: 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, majd 3. számítsuk ki az adott m veleti jellel a kifejezés értékét, majd 4. az így kapott eredményt tegyük a verembe.
verem
A következ szimbólum operandus. Tegyük a verembe! 35
36
9
y:
1
2
+
3
4
-
y:
*
1
2
+
3
4
-
* 4
v:
3
3
v:
verem
4
3
3
verem
4
A következ szimbólum operator. 1. Vegyük ki a veremb l a második operandust, . . .
A következ szimbólum operandus. Tegyük a verembe! 37
y:
1
2
+
3
4 3
v:
3
-
38
y:
*
1
2
+
3
4
4 3
v:
verem
-
* 4
-1
verem
3
A következ szimbólum operator. 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, majd 3. számítsuk ki az adott m veleti jellel a kifejezés értékét, . . .
A következ szimbólum operator. 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, . . . 39
40
10
y:
1
2
+
3
4
-
3
v:
3
y:
* 4
2
+
3
4
-
* -1
-1
v:
verem
-1
1
A következ szimbólum operator. 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, majd 3. számítsuk ki az adott m veleti jellel a kifejezés értékét, majd 4. az így kapott eredményt tegyük a verembe.
verem
3
A következ szimbólum operator. 1. Vegyük ki a veremb l a második operandust, . . .
41
y:
1
2
+
3
4
-
y:
*
3
v:
42
1
2
+
3
-1
4
3
v:
verem
* -1
-3
verem
A következ szimbólum operator: 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, majd 3. számítsuk ki az adott m veleti jellel a kifejezés értékét, . . .
A következ szimbólum operator: 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, . . . 43
44
11
y:
1
2
+
3
4
-
y:
*
3
-1
1
2
+
3
4
-
*
;
-3 Elértük a kifejezés végét
v:
v:
verem
-3
A következ szimbólum operator. 1. Vegyük ki a veremb l a második operandust, majd 2. vegyük ki a veremb l az els operandust, majd 3. számítsuk ki az adott m veleti jellel a kifejezés értékét, majd 4. az így kapott eredményt tegyük a verembe.
verem
-3
Az eredmény a verem tetején van. 45
Kifejezés lengyelformára hozása
46
Lengyelforma kiértékelése
sx,dx,x:read; y:=0; create(s);
sy,dy,y:read; z:=0; create(v);
sx = norm
sy = norm
dx = operandus x = ‘(‘
dy = operandus
x = ‘)‘
x = operator top(s) ≠ ’(’∧ top(s) ≠ ‘(‘ prec(top(s)) ≤ prec(dx) ∧ y: push(s,dx) ¬ is_Empty(s) hiext(dx) y: hiext(pop(s)) y:hiext(pop(s)) pop(s)
push(v,dy)
push(s,dx)
op2 = pop(v) op1 = pop(v) push (v, ”op1 dy op2”)
sy,dy,y:read
sx,dx,x:read
z:hiext(pop(v))
¬ is_Empty(s) y:hiext(pop(s)) 47
48
12
x:
(
1
+
2
)
*
(
3
-
4
)
sorozat
y: sorozat
s: verem
v: verem 49
x: sorozat
(
1
+
2
)
*
(
3
-
4
)
Az x sorozat elemei szimbólumok és számok.
50
x:
(
1
2
)
*
(
3
-
4
)
sorozat
y: sorozat
+
Token Az y sorozat elemei szimbólumok és számok.
s: verem
Az x sorozat elemei szimbólumok és számok.
Operandus
v: verem
Operator
(
)
;
A v veremben csak számok vannak. 51
52
13
x:
Token
(
+ 1
) 2
(
-
*
. . . operator >> . . . operator << virtual . . .is_Operand() virtual . . .is_Operator() virtual . . .to_String() .,,
)
3
4
Token Operand Operandus
(
Operator
)
. . . is_Operand() . . . . . . evaluate(int op1, int op2) .,,
;
Operator . . . is_Operator() . . . . . . value . . . .,,
53
Token
A Token osztály: deklaráció
Token . . . operator >> . . . operator << virtual . . .is_Operand() virtual . . .is_Operator() virtual . . .to_String() .,,
Operand . . . is_Operand() . . . . . .value() .,,
54
Operator . . . is_Operator() . . . . . . evaluate(int op1, int op2) . . .,, 55
class Token Token.h Token.h { friend std::ostream& operator<<(std::ostream&, Token*&); friend std::istream& operator>>(std::istream&, Token*&); public: virtual ~Token(void); virtual bool is_LEFTP() {return false;}; virtual bool is_RIGHTP() {return false;}; virtual bool is_Operand() {return false;}; virtual bool is_Operator() {return false;}; virtual bool is_END() {return false;}; virtual int priority() {return 0;}; virtual string to_String(){return "";}; virtual string class_Name(){return "Token:";}; protected: Token(); }; 56
14
Token osztály: implementáció – „includes” #include
#include <string> using namespace std; #include "Token.h" #include "LEFTP.h" #include "RIGHTP.h" #include "END.h" #include "Operand.h" #include "Operator.h"
A Token osztály: implementáció - kiíró operátor
Token.cpp Token.cpp
Token.cpp Token.cpp ostream& operator <<(ostream& s, Token*& t){ s << t->to_String(); ; return s; }
Virtuális függvény
57
Token osztály: implementáció beolvasó operátor - 1 istream& operator >> (istream& s, Token*& t) { char ch; int intval; s >> ch; switch(ch) { case ('+'): case ('-'):case ('*'): case ('/'): t=new Operator(ch); break; case ('('): t=new LEFTP(); break; case (')'): t=new RIGHTP(); break; case (';'): t=new END(); break;
58
Token osztály: implementáció - beolvasó operátor - 2
Token.cpp Token.cpp
case ('0'): ... case ('9'): s.putback(ch); s >> intval; t=new Operand(intval); break; default: cout << "Illegal element: " << ch << endl; s >> ch;
Token.cpp Token.cpp
} return s; }
59
60
15
Operand osztály: deklaráció
Token Operandus
. . . operator >> . . . operator << virtual . . .is_Operand() virtual . . .is_Operator() virtual . . .to_String() .,,
Operand . . . is_Operand() . . . . . . value() .,,
Operator . . . is_Operator() . . . . . . evaluate(int op1, int op2). . .,,
class Operand: public Token Operand.h Operand.h { public: Operand(int v) {val=v;}; int value() {return val;}; bool is_Operand() {return true; }; string to_String(); string class_Name() {return "Operand: "; }; protected: int val; };
61
62
Operand osztály: implementáció #include <string> using namespace std;
Token Operand.cpp Operand.cpp
#include "Token.h" #include "Operand.h" #include "Stack.h"
Operator
string Operand::to_String(){ string digit[10]={"0","1","2","3","4","5","6","7","8","9"}; string s; Stack<string> v; if(val==0){ v.push("0"); } for(int i=val;i!=0;i=i/10){ v.push(digit[i%10]); } for(;!v.empty();s=s+v.pop()) {} return s; };
Operand . . . is_Operand() . . . . . . value() .,, 63
. . . operator >> . . . operator << virtual . . .is_Operand() virtual . . .is_Operator() virtual . . .to_String() .,,
Operator . . . is_Operator() . . . . . . evaluate(int op1, int op2) . . .,, 64
16
Operator osztály: deklaráció class Operator: public Token { public: Operator(char o) {op=o;}; bool is_Operator() {return true; }; int priority(); int evaluate(const int,const int); string to_String(); string class_Name() {return "Operator: "; };
Operator osztály: toString() string Operator::to_String(){ string ret; ret=op; return ret; };
Operator.h Operator.h
Operator.cpp Operator.cpp
protected: char op; };
65
Operator osztály: priority() int Operator::priority(){ switch(op) { case('+'): case('-'): return 1; case('*'): case('/'): return 2; default: return 3; } };
66
Operator osztály: evaluate() int Operator::evaluate(const int a,const int b) { switch(op) { case('+'): return(a+b); case('-'): return(a-b); case('*'): return(a*b); case('/'): return(a/b); } }
Operator.cpp Operator.cpp
67
Operator.cpp Operator.cpp
68
17
RIGHTP osztály: deklaráció + implementáció class RIGHTP: public Token { public: bool is_RIGHTP() {return true; }; string to_String(){return ")"; }; string class_Name() {return "Right parenthesis:"; }; };
LEFTP osztály: deklaráció + implementáció class LEFTP: public Token { public: bool is_LEFTP() {return true; }; string to_String(){return "("; }; string class_Name() {return "Left parenthesis:"; }; };
RIGHTP.h RIGHTP.h
LEFTP.h LEFTP.h
69
END osztály: deklaráció + implementáció
70
A Stack sablon osztály - 1
class END: public Token END.h END.h { public: bool is_END() {return true;}; string to_String(){return ";"; }; string class_Name() {return "End of expression:"; }; };
template class Stack{ public: enum Exceptions{EMPTYSTACK}; Stack():_top(0){}; ~Stack(); void push(const Element&); Element top(); Element pop(); bool empty() {return (_top == 0);}
71
Stack.h Stack.h
72
18
A Sequence sablon osztály - 1
A Stack sablon osztály - 2
template Sequence.h Sequence.h class Sequence{ public: enum Exceptions{EMPTYSEQUENCE}; Sequence():_first(0),_last(0),_current(0) {}; ~Sequence(); void hiext(const Element&); Element lopop(); void first() {_current = _first;} void next() {_current = _current->next;} Element current() {return _current->val;} bool eol() {return (_current == 0);} bool empty() {return (_first == 0);} void print();
private: Stack.h Stack.h Stack(const Stack<Element>&); Stack& operator=(const Stack<Element>&); struct Node{ Element val; Node *next; Node(const Element &v, Node *n):val(v),next(n) {} }; Node *_top; };
73
A Sequence sablon osztály - 2
74
Modulszerkezet Token.h
private: Sequence.h Sequence(const Sequence<Element>&); Sequence.h Sequence& operator=(const Sequence<Element>&); struct Node{ Element val; Node *next; Node *prev; Node(const Element &v, Node *n, Node *p):val(v),next(n), prev(p) {} }; Node *_first; Node *_last; Node *_current; };
75
LEFTP.h
Operand.h
RIGHTP.h
Poland.cpp
Operator.h
Stack.h
Sequence.h ENDP.h
76
19
Modulszerkezet
main.cpp - includes Token.h
LEFTP.h
Operand.h
RIGHTP.h
Poland.cpp
Operator.h
Stack.h
Sequence.h
#include <string> using namespace std; #include "Token.h" #include "LEFTP.h" #include "RIGHTP.h" #include "END.h" #include "Operand.h" #include "Operator.h" #include "Stack.h" #include "Sequence.h" Token* next_Token();
ENDP.h TEMPLATE
int main() {
TEMPLATE 77
main.cpp – kifejezés beolvasása
78
main.cpp: átalakítás //A kifejezés átalakítása lengyelformára x.first(); while(!x.eol()){ t=x.current();
//Egy szintaktikusan helyes infix kifejezés elemeinek beolvasása Sequence x; Sequence y; Stack s; Token* t;
ciklusmag x.next();
t=next_Token(); while(!t->is_END()){ x.hiext(t); t=next_Token(); }
} for(;!s.empty();y.hiext(s.pop())){} y.print();
x.print();
79
80
20
main.cpp: átalakítás - ciklusmag
main.cpp: átalakítás - ciklusmag
if(t->is_Operand()) { y.hiext(t);
} else if (t->is_Operator()) { while(!s.empty() && s.top()->priority() <= t->priority() && !s.top()->is_LEFTP()) { y.hiext(s.pop()); } s.push(t);
} else if (t->is_LEFTP()) { s.push(t); } else if(t->is_RIGHTP()) { while(!s.top()->is_LEFTP()) { y.hiext(s.pop()); } s.pop();
} else { cout << "Szintaktikai hiba?" << endl; }
81
main.cpp: kiértékelés
82
main.cpp: tárterület felszabadítása
//A lengyelforma kiértékelése Stack v; y.first(); while(!y.eol()) { t=y.current(); if (t->is_Operand()) { v.push((dynamic_cast(t))->value()); } else { v.push(dynamic_cast(t)->evaluate(v.pop(),v.pop())); } y.next(); } cout << "A kifejezes erteke: " << v.pop() << endl;
83
//A dinamikusan lefoglalt tárterület felszabadítása for( x.first();!x.eol(); x.next()) { delete x.current(); }
84
21
x:
x: (
+ 1
) 2
( *
3
)
(
+ 1
4
y:
) 2
( *
3
) 4
y: 85
86
main.cpp: next_Token()
x: (
+ 1
) 2
( *
3
) 4
Token* next_Token() { char ch; int intval; cin >> ch; Token* t; switch(ch) {
y: 87
88
22
main.cpp:next_Token()
main.cpp:next_Token() case ('0'): case ('1'): ... case ('9'): cin.putback(ch); cin >> intval; t=new Operand(intval); break; default: cout << "Illegal element: " << ch << endl; cin >> ch; } return t; }
case ('+'): case ('-'): case ('*'): case ('/'): t=new Operator(ch); break; case ('('): t=new LEFTP(); break; case (')'): t=new RIGHTP(); break; case (';'): t=new END(); break;
89
90
23
