代入以下代码,得:11,9,4,2,1,6 滑稽~
, @2 ]1 W$ W& |" I" A3 v% e( Q5 V+ M8 J- w B4 O4 C3 j n
#include <iostream>
4 |! _2 G9 d& }8 g8 w& P+ Y- R1 I' N$ U#include <string.h>3 J8 L0 }! \/ A% F
using namespace std;' a$ X. ~$ `2 U, q7 w
template <class T># s! ~& Y k$ I5 h, x p
class Node, Z" J. H0 W I/ S4 w5 C& {
{2 l6 L0 ^ F( u) |2 p4 f
public:# q, X* U0 }0 u6 E9 L
T data;
/ j4 L/ O; P+ [ Node<T> *next;
5 i$ k* G& {& c+ l Node()# u$ J+ `& l1 m/ w& i
{* o2 ^ D# q2 @( l7 u8 @( m, t; j$ g
this->next = NULL;
' v! J3 }) @$ O7 j8 V }
# x6 w% G; `1 ` Node(T data,Node<T> *next=NULL); q& W7 k/ v5 ?$ C7 H, Y" R1 v
{
" x: Z& r( u6 G this->data = data;7 |. ^, k" l8 h4 @2 ~
this->next = next;0 L% x4 H0 G# ?! O% L
}
- E; ^! Q( I4 I( d+ j2 h9 r7 W};
5 J9 o. \+ ^( k% b+ x' m8 H8 G% f- M8 U+ L' Z, @; h4 @
template <class T>* q; q1 P, M! I( q H
class LinkedStack
$ P B [* u) e3 b+ E{" ` i# B. I" {
private:( Y( G: k; Z$ c* h
Node<T> *top;
7 p/ J, k; X- M R. u- O0 b1 Bpublic:
1 x. I6 h( \ L2 J1 u LinkedStack();
: N6 D6 Z' y4 T, s5 ~! T1 B P% h ~LinkedStack();" s6 w0 P2 X: K' h9 ~* r" Z6 Z. i
bool isEmpty();8 Q4 z3 n' W$ X0 W# C' H% q4 u4 j
void push(T x);
+ L( @2 D# v4 f! K: k6 v5 D T pop();
( Z7 @ L3 D9 o T get();
6 }/ @, o1 c8 [9 o$ [2 E};5 p9 ?7 C& S4 R/ F& |, ~1 ?
: t& W4 G3 Y3 M- t) B6 m
template <class T>! b2 c6 o6 N2 S/ e
LinkedStack<T>::LinkedStack()) \' s+ D7 Z, T" b! P! m
{1 Z6 z- f* ~8 P" P' Z b8 H& q
top = NULL;
6 j% @, O* `, y6 V ]5 ^}: D. o |2 \; V6 B/ ~
4 _8 f# N( G: v" Y9 O
template <class T>6 \5 p( `' l; O- t5 j
LinkedStack<T>::~LinkedStack()
5 z6 Y7 [: h! Z. [$ p{
) j' a" I2 f3 }* q Node<T> *p = top;
) k, r- G/ U) ?9 U: j* F" S6 { Node<T> *q;8 Z; d3 l3 j* c$ u3 V
while(p!=top)' |! x9 F c; U- U) [
{( z* |/ S4 @& s: ~4 y
q = p;6 I" L# t$ J3 P2 y; j: A X0 g
p = p->next;5 B9 Z) i) k: b3 Z. w' W( f! s
delete p;; [( k! D* d$ ^
}
, L, ^5 P, c" O, C7 k) J top = NULL;# N& l( e# j. t2 K
}' Y5 J% b% ^; i8 O
/ P" |5 s4 m" `. T1 y" F0 T/ m9 Y
template <class T>
3 O6 a8 q6 o, G. T# _, |bool LinkedStack<T>::isEmpty()
" B8 ?7 y' ]- ~( \, L9 \& \{; Y7 W4 D1 F2 F
return top == NULL;4 n6 W i R0 a
}9 }1 K0 {+ b- G6 k' c
, O: n# w! o+ B4 Mtemplate <class T>, F6 X$ \! g$ R% M$ O0 k0 r# U
void LinkedStack<T>::push(T x)3 b6 U% ~. j1 h0 p/ T
{9 P4 q6 M O+ K6 ]4 H1 L
top = new Node<T>(x,top);
$ k1 u7 h7 e3 W% a( v8 m! Q}# f" A, v% N3 M! k0 k
6 ~4 b2 m- N: Q: _# [2 Z, j5 x9 {- n
template <class T>% A. O: ^2 s% s/ L; k3 u1 p* b
T LinkedStack<T>::pop()
$ Z w# \$ ~+ F: a, K# g+ S( u{3 n4 n+ e5 @0 R5 X+ i* k
if(!isEmpty())
$ g" Q, }& a- ~ X& q/ N; ] h {9 A0 ~$ q! P" ~
T x = top->data;7 w7 V* R: W' ^3 r; ?
Node<T> *p = top;
% x# g$ i+ r' c& x top = top->next;
5 y$ w; O6 C9 F% W( |3 j. n delete p;; z, @1 C r3 b8 j
return x;5 x8 X8 V+ Y/ C' n
}' H% L' b- J, B/ t
throw "空栈,不能执行出栈操作";3 C, Z6 ^' p, z2 v! f. [9 Y
}
: W6 V: `7 ^ p# L8 o3 q# z, m; a
template <class T>
" K7 C8 [& r" j: ~) s5 L' C8 d4 r/ vT LinkedStack<T>::get()
6 s- l: Z' `1 b w* D& U2 ?, H9 N" S{$ }; N5 }4 Q+ n$ m& F' }9 ]' l
if(!isEmpty())
: n5 k& ~' U% P" S- k) Q {( }- w2 b# j8 z* k/ K' Z
return top->data;; }1 Q/ z- [0 Q' o9 B' @" o, T# G
}
& c% ]/ M3 w+ V5 K; L throw "空栈,不能获得栈顶元素";6 w5 e: R6 s5 ?. x( ^. X5 P$ r' g
}
* g# k' Z- j# h4 P8 S3 ^ w# \* h9 V& [
% X: }6 v/ o( m, C! mchar * toPostfix(char *expstr): ~7 @1 F& M4 |7 h& J
{2 z R( @4 O( o& H! m. X
LinkedStack<char> stack;# Y/ S* R3 c* d# n' n6 J
char *postfix = new char[strlen(expstr)*2];
1 o6 U: X& G9 p$ S int i=0;
9 P5 |$ q' k, J: }9 e# j int j=0;( T: y$ V( U! O7 u# w+ A; u. G2 h( C
char out ;. @1 r, Q! `( P" O
while(expstr[i]!='\0')
2 y. S9 ^+ g; W# u4 j! K {" H0 h: t0 g9 ~$ [+ O! C
switch(expstr[i])
8 v* U. x8 A+ B9 ~ {
* L+ Z9 y* N7 E. r i" M7 L case'+':
& t; q7 F) Q, L! ^. S% X case'-':
2 r- l, i# R! L" f) u# U while(!stack.isEmpty()&&stack.get()!='(')( M2 ]1 {3 G2 k! c
{9 h' Y. J6 e. D5 j' ?8 S& N+ P
postfix[j++] = stack.pop();! P$ o% ^# o: o- e/ m. S
}
; a' h* L1 e. f' v1 Q1 L stack.push(expstr[i++]);
R- l. @& _, I. L! S6 P3 m6 Y break;
. y! k! X6 C! b( N case'*':- `2 ]- Q- {$ v; ^' X9 A
case'/':
- y! F/ W( n9 _1 H) ]6 \1 m1 p while(!stack.isEmpty()&&(stack.get()=='*'||stack.get()=='/'))
9 w- @6 d5 V8 E6 d. j7 D; g" i {% D. A, r d* u7 \- `
postfix[j++] = stack.pop();
' ?2 ]% m+ h6 ]" w5 H }2 ?2 C8 n& m# [0 n8 S
stack.push(expstr[i++]);
" B/ ?% s# V, j: L, D: ` break;
5 n# h4 n& A( ]4 ^% Y; {. ` case'(':stack.push(expstr[i++]);! X# ~; \8 K! k4 h, g/ {+ p
break;5 A! S* Q7 W! [. f8 x" J; o
case')':out = stack.pop();" f! l& _8 P* `% B
while(!stack.isEmpty()&&out!='(')
+ f: R4 _4 ^1 g8 b2 d/ u {4 F# z5 b6 A! L$ h8 w* @
postfix[j++] = out;( h! ?+ t' z7 z9 j$ Y9 R V* K
out = stack.pop();
, k4 H8 _7 U, t! I, k+ Y }: e' P2 t' r& h J' C- t0 a+ \) e
i++;
8 E, J/ U8 y8 m6 r w4 D% G break;$ f% d3 k% s% T8 J' f$ }8 r. w
default: X: O: \. {$ Z# x
while(expstr[i]>='0'&&expstr[i]<='9'&&expstr[i]!='\0')
- {. f0 x5 ^3 y- p* i0 T1 F {
+ T! A6 J5 e: j4 a' N postfix[j++] = expstr[i++];
1 }0 }# r% f z4 V" \! N F; `2 b }
0 v7 j7 i ^; k$ v: Y postfix[j++]=' ';
! H( x7 P, K* C; l- `$ d break;
$ Z, ?" j& Z, C) D3 e }; U4 W0 j8 C2 o) [: s; Z: a
}
v- s4 G) Z; X1 r9 f while(!stack.isEmpty())1 ?1 ]7 Y+ R! ^) g+ g4 i- Z- { P
{
7 F% y5 b: Z% ` postfix[j++]=stack.pop();5 X O& U# ]* p
}
1 x4 c$ b Z: o. e, o postfix[j]='\0';: f/ C% x& t: S9 I- J }$ ^
return postfix;
# T+ X( `- G, d, m7 o}
) [$ J$ m1 x' ~9 m; z! u$ @
8 m% l1 T8 k+ n$ d1 y) Bint value(char *postfix)
5 A8 L; Z/ h8 o# G. k{* l; J0 {/ y: }# [' N3 a
LinkedStack<int> stack;+ m, B. X' \1 u) q& k
int i=0;( U* T& o; |) o! W2 c
int result = 0;
/ o' I ?) F3 x/ U6 y: u while(postfix[i]!='\0')
3 c/ ` b3 `, p& Z: H p {
9 s. i$ i+ G% T if(postfix[i]>='0'&&postfix[i]<='9')4 E6 P: N0 g2 [: _4 I+ C5 ]
{
' k7 s; b/ C4 x: i result = 0;
" ]( B1 U* L3 g9 R# t while(postfix[i]!=' ')
7 Q! c/ N+ B" ]' R% Z# } {
7 q6 h% t# ^, [2 W/ e* G4 Q result = result*10+postfix[i++]-'0';
8 Q( d3 L3 {; n i, |$ O; H/ J }
8 a, e: i% B5 `( c M; k0 y7 D i++;% W& D% }0 j3 U+ G6 n' I. k3 e4 p
stack.push(result);2 B/ U i. T5 U( W' b
}- K2 z& ]7 k4 l' S3 M: m
else
0 Y N/ ^% L8 ` B8 T; q9 ^- [8 f {
9 G9 ?6 J' k( z7 r if(postfix[i]!=' ')3 e7 h. E$ V+ u& \, O
{
( E: b/ i- d; y5 L$ N int y = stack.pop();
& n/ e: ?2 z' T) S( O int x = stack.pop();
_7 X2 h' h b switch(postfix[i]). n- p7 F, X. F. z8 _
{# c5 |3 p+ p; L+ |3 b3 d+ K7 C4 z
case'+':result = x + y;$ M. ?" a# p7 R# e
break;
) w: o+ U; C3 G8 ^7 E4 Q$ K+ t1 s case'-':result = x - y;& ]" V1 p" e, @2 u N4 u
break;3 O8 ^2 n2 u4 Q, k9 m! K6 p% H8 ]9 y y
case'*':result = x *y;) {* W9 S1 R1 i9 q4 m. |
break;
4 {' A( Y/ l9 h+ G9 @) G$ W! P case'/':result = x / y;9 g Y, v; w v% {8 J& O: N
break;
$ v6 K) G+ ~5 l0 ^8 f }
9 K7 ~% y5 L1 _ stack.push(result);7 h" J$ O2 `$ v+ d
} ]* Y) |0 z1 I; }& {$ P
i++;# }3 V% `' B- e# I( L% r
}
3 g3 f1 B. D+ g9 o* M; @ }% q! Z6 C3 z9 }2 _0 b
return stack.pop();1 y, `6 O3 a* Y. R+ K; p I2 y1 H
}: I* _1 I0 ?" p) Y! @
+ T* U! S$ J8 Z q
int main()
, U, x* |& z% F7 w [# k6 ^{
+ L. E5 ]! P1 ?. _7 r1 M //char *expstr = "121+10*(52-49+20)/((35-25)*2+10)";
% j* s8 G* R8 |1 N5 C1 W cout << "请输入表达式:";: X2 S: Z0 c; ?
//char *a ;
4 g+ v% r1 l, h //cin >> *a;3 p2 E" h# u, t
char expstr[20]={0};( A7 a1 }9 G8 l0 n" V9 N8 t7 U( {9 c
while(1), F' k# x' r1 Z
{
9 g) c3 u+ x2 X/ l' K cin>>expstr;
2 x& C0 T4 ^3 ?. R1 X+ Q8 S char *postfix = toPostfix(expstr);, f. [7 i" N9 W2 z0 c$ f4 `
cout << "expstr= "<<expstr << endl;, T6 R0 ?# K# O8 l5 X
cout << "postfix= "<<postfix<<endl;
7 W* [1 d6 S6 R) _9 [' O cout << "value= "<<value(postfix) << endl; K; |# W* Q3 L
}
( H- j. A+ P: d/ f1 S3 D* s return 0;
- f3 v- Z- K: C3 d} |