代入以下代码,得:11,9,4,2,1,6 滑稽~
9 I& ?. o6 I9 {2 M( @$ V" R+ j* N7 J6 {8 U6 n
#include <iostream>) _. H3 ~! [& S/ {1 |+ v' I! H. j
#include <string.h>
+ c X# O5 t7 }# D% i2 Xusing namespace std;8 W J. q1 z% M ]: E7 d* M
template <class T>9 O, B4 j3 T: z# y! _ x4 e
class Node
* _* k- l( M9 \{
" B" Z! M9 p: E$ mpublic:$ _) a. b& [9 L R: n
T data;. _; ]. A. W5 L
Node<T> *next;
6 G; E: `$ K! ^7 i3 X [( G Node()& a3 o9 w- S$ Z1 X
{' k. H! @+ x8 B4 }9 A
this->next = NULL;0 q `& ~2 Y" f( A1 X% w
}4 I( U* u) v; c2 v
Node(T data,Node<T> *next=NULL)( j* z' V9 q9 S! z( L% g8 Y
{
W- L; ]/ d/ e3 F" ~) e this->data = data;
# Q5 H! v5 W. q) W- ]/ n3 K5 H7 z this->next = next;4 {1 X* S) H1 o9 f
}
0 g8 I# M* s/ @* {4 I) f3 j};8 [6 x/ E6 d6 v3 q5 V
, n! r" [2 X7 s" o# q& W
template <class T>3 D& s) |; X( k1 Z& o3 K
class LinkedStack. o5 }8 a0 j* z) K
{$ e2 p3 F# @9 [1 K3 M0 J- K- y% o
private:! G' m2 {+ C `% X+ E% M
Node<T> *top;
* o0 D- v1 N2 u2 L5 npublic:" D9 a# t% V2 o) _0 \# s
LinkedStack();9 ?' o% @& [6 H5 l7 I/ O& c
~LinkedStack();) t3 |' g& g+ A4 |# I9 K
bool isEmpty();
) J+ u. F' H# k! J& q void push(T x);
9 r+ l* [. C( q. {# i ~ T pop();
3 U8 d% v, B( g H4 w9 }( A T get();7 q+ W) _/ r$ X$ z! ~0 Z0 f
};; H$ q- a/ S4 t- f
+ M- J1 q6 t! ~, C% \2 stemplate <class T>; x0 \ M# _8 o% [2 S) O0 b H( {
LinkedStack<T>::LinkedStack()
' S7 | k+ Z5 F3 ?3 R* S# W/ H{3 o2 S# D3 ?) i; {4 _
top = NULL;
/ |6 |2 f3 g3 k, N}. V7 `. l! u: f& f& v$ p, M! N. w
7 \9 N% }2 H2 R3 g- ^
template <class T>
" K. t, W7 I- d) E9 ZLinkedStack<T>::~LinkedStack()3 V# }$ T* r( |* X/ t1 t+ p
{# v8 X @5 q: D6 {# D
Node<T> *p = top;( }6 c9 l6 ^& j, Y \: I; x$ \- C
Node<T> *q;" j* \2 j! [( V+ e* {
while(p!=top)# q* b* N5 z5 w
{) w3 |7 S g1 j( O
q = p;
& ] w8 {; \+ E, e p = p->next;% t `; v! G% Y# V3 N' Z& _
delete p;
1 I- T) |: q& Q; Y3 L3 T. A% c ?7 Q }
9 e: Z- {/ ]* W" B top = NULL;
( y2 s" D* Q8 g* x% \; n: ?}3 K7 Y" O v7 n4 J4 h2 c
4 b. D. N. S _# A2 [' `
template <class T>' i1 ?# s" Q, ?1 }3 Y( W
bool LinkedStack<T>::isEmpty()
* r) a# W+ W# n{4 h! o$ h( P. I
return top == NULL;( ?) J2 {; \( J9 t, q3 b( G% S
}
8 O& B9 A3 F" u' L5 i0 [2 i9 Q0 _
; F0 p2 [# E! A4 Y9 d4 itemplate <class T>2 W3 |2 B+ U) q4 t( L1 {: }
void LinkedStack<T>::push(T x)
8 Y6 |6 L9 a/ u1 G# s{
! y. l# {1 V D/ G top = new Node<T>(x,top);
+ D9 j/ h! I1 z- S/ m' w. z}
4 {* Z! I0 G1 T
& L1 @0 _7 {* E5 q2 a9 r- Ptemplate <class T>
9 b! {. J' E$ \# g$ a% l/ l* D5 yT LinkedStack<T>::pop()3 K4 H5 e3 @' p, ]& P5 n# ~
{
" X4 J# ?9 N& K7 D# [ if(!isEmpty())
( T2 k# n. I/ g, S, w {7 b! c& r) M. @* G
T x = top->data;
- d7 J% o) g. ^8 C% l: ^ Node<T> *p = top;
: J% J% t% a; J7 [4 l ]$ d7 O top = top->next;
7 i8 A' h: ?0 L* X, { L& J+ _9 L delete p;
* u" b6 S* A( Z* }0 H# ? return x;; o! @! n |- g: R0 {; i" _
}" W; E" e' R/ E# y; e1 d" o3 }
throw "空栈,不能执行出栈操作";
1 m$ W' A1 o: f0 o+ p: F}3 j# {; K W2 ~6 l
8 ]9 Q+ I( A0 L' H0 Y* y
template <class T>& b- M% S9 N5 }5 C4 t1 X
T LinkedStack<T>::get()7 P% r! ]# s6 ^9 G
{
$ n/ r% f, ?5 E6 d9 b" g if(!isEmpty())4 i$ G- p/ t! S7 @) f
{
& g" \/ ?; N- N return top->data;
, h- O" E: ]7 w9 l$ G7 o }
9 Q5 S) N3 \4 j$ L6 H1 L throw "空栈,不能获得栈顶元素";& l5 t) t+ K- m( u! q" b' t
}
! T: O/ w) F( [- y' w8 ?$ X
+ g) D7 U( D7 {& n8 r6 D2 Ichar * toPostfix(char *expstr)5 o, |8 ?' B& h. V% q5 h, D- y1 c
{- j# V i; B/ @% n# O7 n6 E+ B
LinkedStack<char> stack;! j2 D2 g; w: v! ~1 ]# q$ e8 p1 V
char *postfix = new char[strlen(expstr)*2];
/ l: a, W, l6 h! o7 r2 q& D int i=0;
9 \& q" w, w$ P: N: K# N8 ~ int j=0;/ c6 ~; [ {% R
char out ;
6 R# ^7 a2 f9 i2 F4 ^ while(expstr[i]!='\0')
/ g( `, m+ a5 T. O7 z. c/ m0 Z {8 @! `5 V% m( H, V( G5 J: M
switch(expstr[i])/ E: E! N$ _6 j! }$ ?; C/ K, ~. ^
{9 ?, k. x' _( ^% g( v7 ]( D O
case'+':
, {! g; I- g9 W% S0 P, x+ i4 \ case'-':
. `& w2 F- V0 k' f; o while(!stack.isEmpty()&&stack.get()!='(')/ `4 P" ]5 y. S# N
{: m O% O/ j% m" u( H
postfix[j++] = stack.pop();( U R6 U3 B6 k! A4 E5 j5 }5 `
}% |% B7 [2 K6 g
stack.push(expstr[i++]);
% ~3 V& ^# ]+ J ? break;- d; q; |# {! U
case'*':( |4 J$ y ]9 J2 X" R% a/ W3 j
case'/':/ r/ f% `' f( y' H
while(!stack.isEmpty()&&(stack.get()=='*'||stack.get()=='/')). j# T" P! P3 A; n% @
{
( d% U: R( q$ O- d$ K* P; K postfix[j++] = stack.pop();
: N/ U( {& b1 [" \( n }
7 x! B; v2 f) k8 ^4 f stack.push(expstr[i++]);
: N% J$ v+ X8 V2 u5 r- ?. D break;
* W) y9 p0 b, I- L+ B q4 f case'(':stack.push(expstr[i++]);
9 f0 [- O& H4 R4 p break;
L" q8 Q$ p7 c case')':out = stack.pop();) Q! ^/ d: K8 Y) f
while(!stack.isEmpty()&&out!='(')) G# z6 P& z0 @3 e4 m, e) ^
{
& R0 F' A$ x* R postfix[j++] = out;
3 ]# o5 u8 C2 Z( c) ? out = stack.pop();9 y) U; u- f; J8 Q" |9 F
}) o6 h/ W0 c! h8 N
i++;6 N5 i' L% j. Y- T
break;
$ y/ K# T6 N$ o1 h0 w9 ? default:
5 ]4 W& Y' h% C, Z* N while(expstr[i]>='0'&&expstr[i]<='9'&&expstr[i]!='\0')
/ k& D& b9 `, i/ k {
9 t$ J/ ~3 Z: |1 D, B postfix[j++] = expstr[i++];2 s9 ^& Z2 X {
}( m' E; _8 R3 P, \& F7 N0 h3 G
postfix[j++]=' ';
- R/ Y5 M: |& E; A6 N$ T' f {3 M break;
# {) q6 s$ l4 l5 N+ h. S+ z( p }
& ~6 H9 H2 H+ r4 W }/ ^1 c9 O& d4 \
while(!stack.isEmpty())
* {; {. B: G. R- V$ X P2 r {1 Z, H6 p! J% [$ N
postfix[j++]=stack.pop();
$ Y9 B$ B$ v0 X3 T) ^ }
% B& ~5 v8 X6 L# M. ] postfix[j]='\0';
* f0 \- ^8 P# D: I! h return postfix;$ q2 H3 J4 d0 q# V2 m6 z$ W
}
2 c: ^4 V' z9 P' B$ ^, Q; a0 f. v) \( R7 w, {
int value(char *postfix)4 a( v: w3 i1 o! B* B0 {1 E
{9 r, o, I( r$ b3 ?
LinkedStack<int> stack;
! ~9 N8 k: v+ D" X. s int i=0;
6 A) }5 m) Y8 c D int result = 0;. W, {3 s/ R. d5 B8 _3 r
while(postfix[i]!='\0'), n1 Y0 h+ D2 k4 s* A$ i3 ]& E3 e
{. P; h3 [( i# R5 P
if(postfix[i]>='0'&&postfix[i]<='9')6 k" a5 r' P+ [; w* U6 m
{/ Y" e2 m8 ^! w0 p
result = 0;- ^* ?9 J% j M$ w# k8 Q/ T4 F
while(postfix[i]!=' ')) z. A8 a/ k# g V' Y$ G
{6 q5 B9 v, O% P% x9 Y+ ^' c( q" K7 w
result = result*10+postfix[i++]-'0';3 P5 f2 z8 @* v: g6 A* r
}: z$ j. f5 |* e- R( ?, T U' b, q
i++;# k/ M5 w: L' S* I
stack.push(result);. ?% T! |5 o9 W
}% K- e( M1 H5 }# L+ A
else
- S5 H! O" B; v: K/ M/ X8 _ W( j9 @4 Z {
# M8 }6 g: k$ f& K0 y- H( D9 t7 H O if(postfix[i]!=' ')
- R$ G) V6 B2 \0 V/ R {# X9 b! O; e6 Y, t4 p! y
int y = stack.pop();
% P( Z( Y: v) q' T1 t int x = stack.pop();3 u; ], n( r: b5 O3 A
switch(postfix[i])/ B, H- l" ]! {1 B" m
{
) s5 W2 B9 x! @ case'+':result = x + y;2 o5 {6 _) p! n( G+ f) B4 {0 Q& t: `
break;
! f: l+ T+ m2 Z case'-':result = x - y;0 B1 [3 V! P8 c, P
break;+ R7 _- q. V- G& ?. H9 {
case'*':result = x *y;
9 j4 b j" D$ B6 ^3 m break;. Q9 {+ l- H7 L7 S
case'/':result = x / y;. @5 T6 A5 P- G
break;/ _* e# i, ^2 N: Z3 c; l
}' X9 \/ e0 L+ U8 B d) E! f% L
stack.push(result);2 a3 U" h* g% t- F7 f3 H
}* W) Y; Z$ T. h7 D% ^
i++;- ~* d# d6 f% v" I3 w! I+ F
}
' ~3 b8 M, Q* ?2 Z( [9 ]& \/ U k }! d& P; j% f; v
return stack.pop();
# {9 W! E. F4 P# m}! V5 F8 e# C' I
8 n$ U5 i; t, L% R
int main()6 `% }8 i$ t- X' s8 N6 b+ i
{ J3 S- M! i, M; @% B# d9 ~: L
//char *expstr = "121+10*(52-49+20)/((35-25)*2+10)";" P5 {7 s9 `# `" q; J2 A; t
cout << "请输入表达式:";7 \/ Q; ]" S% Y# L; \0 R; \
//char *a ;8 m% S/ e# y# W3 T
//cin >> *a;
, p9 U7 k3 C9 O5 b( n4 x char expstr[20]={0};
, {$ J7 u9 h' m1 n9 N9 x& E while(1)9 a0 B+ P) y2 N$ S a
{
; I) r6 r+ B( a$ j, a" S" R cin>>expstr;
q3 }$ {, Y: b char *postfix = toPostfix(expstr);
N1 P: j, P; h7 _" @" H cout << "expstr= "<<expstr << endl;
: k3 I0 c# k X$ A, W cout << "postfix= "<<postfix<<endl;/ x. O) c5 O# T# }+ H! Q0 N2 O
cout << "value= "<<value(postfix) << endl;+ B+ u. R& X) N+ v, J0 l; O) \
}7 g! r* d! y! ~9 E6 [5 S1 ?
return 0;
) |' J' X+ ?- c( ^; C0 Q, ] m} |