代入以下代码,得:11,9,4,2,1,6 滑稽~
4 ] `% |8 o# c- g3 w; B
* x% n+ L& _" c8 n3 |7 p#include <iostream>
`: r8 ^/ ^1 D$ I) [1 Z4 L#include <string.h>/ c( `" {# d! J
using namespace std;* {4 Y; R/ \3 F
template <class T>
0 B' ]3 C: J/ ]: Aclass Node
; y8 z7 F1 F2 b; ~{
/ l+ A- H! k% `4 W8 g9 ~, E. _public:+ \5 t( u& h0 F Y8 t! y/ ]
T data;
+ D- z3 `& L8 e Node<T> *next;& f0 u' Z* g8 U6 x# N0 @
Node()
& O& C% `, R6 ]6 X4 I {6 h# f1 i0 [6 S' K+ [
this->next = NULL;
. U/ T& u$ f8 V: ^3 i }
4 E7 l, H/ T' j" g( Y) | Node(T data,Node<T> *next=NULL)2 h6 _( c& t% x6 B1 n
{. R; x$ d9 X: p7 b; u6 ?
this->data = data;; l0 Y6 o' j: I% T5 s. o, J. J
this->next = next;
5 \/ Q r1 {- o6 S- g9 O! C }
) X4 ^ N0 o' L* j1 I& ?, @. I/ h};+ O4 W/ S# i) p- e
: T1 r1 K8 a, a
template <class T>
) n' U* P( m r3 q* T; K/ C$ m& fclass LinkedStack
) | k9 [. L! S{
0 b3 Q9 D/ _4 ~) |private:7 R, x7 B* g+ O2 m6 B% @) r) O
Node<T> *top;
1 w! b) D+ U6 k+ d9 C* Jpublic:6 T! z3 P# ~, Q [8 v2 `) p) s; y& o
LinkedStack();
6 q# Y2 |' b; x ~LinkedStack();
& N! r$ v) k- K: _- Z9 L( J bool isEmpty();2 Z& ^$ C" G S C, z
void push(T x);
9 ~2 U1 z) Q9 J+ x% H' l T pop();# }) S5 R+ o5 y1 |' r- v( r* x7 K
T get();
0 x1 w/ Z5 t# ^, t- W. U4 |# E};& l" d i B6 }3 ` E. U9 `
3 ^% i4 }% I" e! ^! o" X' c% Z2 w
template <class T>! q: U' X$ A( o$ a
LinkedStack<T>::LinkedStack()
; B& ~( x) \4 K% e. J% O& w& g8 i% [{
6 N4 ]5 P4 T. G3 U8 l. l1 h4 z! s9 I- q top = NULL;. a7 n& ]1 \- k6 l& ]3 Z# @& l# [
}+ _: E3 G3 I, D
$ D8 P! U% Q. O% }1 t: V
template <class T>
* I R0 t; k0 a8 U4 }* K, O, U4 YLinkedStack<T>::~LinkedStack()
& X) P/ c/ `& m ^: X$ Q+ L{
& m6 t# g6 s% M2 ] Node<T> *p = top;
5 n* N: r+ V+ s7 G0 m+ U% x; O) Z1 g4 \& E Node<T> *q;
8 B4 B1 S$ p$ A8 Y8 C, f while(p!=top)9 z, d0 F3 Z" {
{
3 r' r+ |3 ~ @ q = p;
2 C/ O+ Z9 m2 \8 V5 X p = p->next;) S5 l' b- h$ V5 M# v: K2 I# O
delete p;
2 j3 ?: `, j6 }$ C% V$ Y! r* e }. q9 X7 x7 w7 c8 T. D
top = NULL;
4 Y8 }' N) \; o9 A( a( r}
1 C! @) M& h$ M# ~5 O4 E; i9 Z/ s+ _' `% ]4 @+ s) Z
template <class T>
3 S/ X6 r, @; i+ Ibool LinkedStack<T>::isEmpty()
. ^" N3 X2 Q( u" T% {* O/ y o; Q{3 H, D) k. ~$ ?, O' h9 ?9 s. D4 [
return top == NULL;
1 c: k( x! c0 G& Z- j! o5 m}
; h1 [1 d# {8 j) t+ a- y9 w# q E3 r; y# T4 u
template <class T>
8 x( \+ M' [( a- fvoid LinkedStack<T>::push(T x)
( q: g+ q& |0 S{
* H/ F$ ^- A* |% v2 D. N a top = new Node<T>(x,top);, Z( q- } E8 v. F) U. i6 ?
}
. E) `& Z" y$ y5 r8 z& f8 C
3 t9 O$ i2 l8 Y) G9 \1 `; Ctemplate <class T>9 g y( F" d# w9 W; z7 G A" ~
T LinkedStack<T>::pop()% R! H( s1 t3 L4 ]# f
{
; c$ ~( N/ b; t: R0 a8 u& j if(!isEmpty())
3 Q- p) N: \) `5 a6 y {
/ V7 t# }/ o: {% R v4 @+ o1 C! o T x = top->data;, v' ]. I' N4 n4 L1 ^" V$ A5 y3 A6 u
Node<T> *p = top;& [& U( {1 T8 v: U' O
top = top->next;! M2 i5 B3 O0 }9 {& s
delete p;; n$ I( t- v% y0 G
return x;' d* T$ j( C5 p% Z5 c y
}8 c& v2 M: b2 P! }, A* c Y
throw "空栈,不能执行出栈操作";
# q: O, X9 I' F1 T}
: p% J+ U2 P2 i- ?3 s. c( l- a! F+ P( d1 w
template <class T>
, R3 E' D" m+ wT LinkedStack<T>::get(): m" I" c4 S. [6 |, \$ q
{
0 L- m: v6 j0 X3 Y if(!isEmpty())
' \6 R. w# z' Q: z {
S7 x5 a* T R! y2 N) Q return top->data;5 D ^ |1 a3 A
}
+ t; P6 y" `8 z) N! Z5 n4 d; r7 b throw "空栈,不能获得栈顶元素";, x6 N# w# q2 z4 ^1 H, S
}. \8 f0 y+ \8 ^ _" x
2 B* ?- y" F* R# qchar * toPostfix(char *expstr)0 g* k, I8 l9 l8 C7 E
{
{4 Y0 p: [2 P/ k D; U9 N LinkedStack<char> stack;9 D& f8 n" H& |' n$ C8 u! ^8 r% g; F
char *postfix = new char[strlen(expstr)*2];
# I/ J" \6 `0 X. g+ |6 j int i=0;
9 ^0 I: z) E- F- [! U" ? int j=0;
; |) A' u: o+ A0 I: }9 `( H# a, f char out ;0 m. w5 o5 v) N4 H6 u' S$ O" b
while(expstr[i]!='\0')7 G! u6 t& Y# j' G5 V
{! z3 J* I# r# {
switch(expstr[i])0 w L/ R, G; {( e% R
{
! A. |, ^7 L) B( s8 R1 t case'+':- G0 ?7 ~9 G) ~; `$ U
case'-':" H8 }% P7 Q& W& K$ g/ n
while(!stack.isEmpty()&&stack.get()!='(')
+ n& b, L& J, u/ V {
) @9 E- x2 z# \( t, j postfix[j++] = stack.pop();
5 h& L/ H' o: L g& q* `" Z# C }
( X z4 M+ j* s; j A, W stack.push(expstr[i++]);
$ Q* H5 [( V2 t: m: V break;7 I6 J" C9 _* L& }. i
case'*':
# o% I) f) Q2 f5 x) r' J$ x+ h case'/':/ h7 w. I/ W y8 _' c; W
while(!stack.isEmpty()&&(stack.get()=='*'||stack.get()=='/'))& `& w; q, H, r4 j" q
{6 a% Z2 [7 B% ]" T" Z9 x
postfix[j++] = stack.pop();2 A4 Z/ e4 E! M' r- M- @
}% ~6 F8 W5 j' u0 l d8 F1 J
stack.push(expstr[i++]);
% t2 Z5 b+ @. g* `& `% ] break;. [- L# s' |, [" O: i
case'(':stack.push(expstr[i++]);) @1 r! s4 Y, X3 Z. J: E% w8 G4 R( k
break;$ d( Q5 c0 j1 k$ y9 D
case')':out = stack.pop();
8 O; W, Q. T* E$ [ while(!stack.isEmpty()&&out!='(')
$ h$ l) j# Y) ]" u: t {
' M1 X% C+ h+ I3 n1 e2 z postfix[j++] = out;
3 R+ ~ T, u/ N) r# w% P# O out = stack.pop();- G* D$ ?0 n O$ m
}/ c3 y4 H. M1 [: {* }
i++;
/ E( F9 A, _* H8 _4 D8 E break;
# R: K" w$ c. `4 ?( O- H default:0 j2 B, O! ?9 V) j2 [4 E, i
while(expstr[i]>='0'&&expstr[i]<='9'&&expstr[i]!='\0')
& A0 E! D1 b" S& { {
! ?7 _; F) J8 ~& { postfix[j++] = expstr[i++];. Y- {( B, R3 ~5 T1 e# u2 h
}
2 s+ m) ^* I( \ P: h5 g postfix[j++]=' ';
0 H/ z8 m5 Z! Y, g) S9 x) }$ @& O break;! k1 @ z, k1 R/ m! @
}0 I6 E- V! K8 F0 Y. q; ]
}
7 G+ _. l$ ^$ j2 c while(!stack.isEmpty())- {& r! w% E: T$ y5 ]0 X% O
{/ n) n2 L1 s$ u- P( R# m
postfix[j++]=stack.pop();
; g+ d9 [( ^) Z* Q& u% i }- [- _3 L2 A4 t8 g; \
postfix[j]='\0';
- J* B+ c( Z% H, h2 f+ J return postfix;
+ t* I( X g$ J3 `) }) v7 e}
& n2 M8 U/ e) P/ q4 c1 w/ ~+ D
1 f( M7 y# \8 Y6 a+ R" Wint value(char *postfix)) r/ `( u4 b' D8 H( o. M# u4 n9 n7 x
{1 A) C3 V; A. G5 m' R3 x' U; F
LinkedStack<int> stack;) N0 j1 ~& K0 I8 r; C0 s
int i=0;
1 P9 I, a% J5 Z+ P. E; t: K5 U0 o) } int result = 0; O# h$ Y& y& f4 k( r$ j3 o
while(postfix[i]!='\0')
) m% L8 v5 W+ u( t {
: q0 T0 x- [( B" ^ if(postfix[i]>='0'&&postfix[i]<='9')
& J6 l4 p% A7 F% n: m {4 c1 e5 ^6 s5 c2 R$ r8 Z
result = 0;
) {8 [: v4 `5 v* E, k6 o2 A while(postfix[i]!=' ')% r! ~. H+ u. U. Z5 b. A
{( P: M2 L! t2 l
result = result*10+postfix[i++]-'0';
0 _ }. N7 l m( b# J- _ M }6 D7 _ [6 K$ C5 j) \4 M
i++;7 ^& @5 y, S. W8 ]* Z# [$ p
stack.push(result);' D% g) g; Y# b) k
}
1 f7 U3 ]- J3 H% i+ d5 x" ^ else
5 [2 W3 j& T1 w; b8 Q {& W* h2 h2 [) c
if(postfix[i]!=' ')
" K9 t/ H; T0 G {
& A' s T: S2 ? int y = stack.pop();1 ?$ g& L& |3 k9 Z! s/ D7 f6 o
int x = stack.pop();* Q" E$ F- Q5 ], \7 v! R U$ J+ }
switch(postfix[i])/ z2 a9 Y! u$ ~
{1 m1 p* [( k9 \3 x# D0 v5 s- P" _; ^
case'+':result = x + y;
3 g) }3 L* Q; t. S break;7 C1 a1 p) l- K q4 i
case'-':result = x - y;
& Q# r5 ?: r! z+ ]! D, r( ] break;" o7 }) K& [! q9 R5 E
case'*':result = x *y;
! c- G3 S2 D& y3 b- ^. m break;
) g9 y& l# X0 ]7 h g case'/':result = x / y;9 b! b* T/ ~, H, X8 E; D1 k
break;* S+ H6 O9 }! M a. _+ y4 q8 b. y
}% D( ?3 ^+ J! n) a
stack.push(result);3 e7 B8 s( I% m8 T+ Q
}! ^; l1 S3 W* V6 c0 C% [+ ]
i++;' l6 }1 s# q; u" t/ z" w5 L
}" j0 v2 y4 F1 V; r( C
}) o$ l6 c1 W3 V( L# A2 J
return stack.pop();- ^+ {- _% f9 \
}
; G/ k4 D' ^( Q& g& ~+ H& G4 O6 w& @5 o8 X8 ^6 O+ P
int main()
/ O4 M% e0 b8 b{
, B( j- |7 q, D/ C; s2 G4 { //char *expstr = "121+10*(52-49+20)/((35-25)*2+10)";; B' O0 u# Y$ S0 x! P' M* @0 Z
cout << "请输入表达式:";
5 G9 D$ h4 |+ S //char *a ;
6 e2 s# ^/ R- [6 b9 j1 U& P E //cin >> *a;
3 \0 h5 [* f2 m0 i4 U char expstr[20]={0};/ j7 B+ z( p2 x6 U, J# M$ L
while(1)
8 }' D& O& K' n" X {
; [2 ~4 b s4 S J! A cin>>expstr;8 j+ f( R) v% K& S2 ]
char *postfix = toPostfix(expstr);
& V6 U) a) l" v% {( H8 P, i+ }7 b8 ] cout << "expstr= "<<expstr << endl;
8 X5 O; A8 N+ @9 Q2 ]" l cout << "postfix= "<<postfix<<endl;
0 v$ ]9 `2 u+ L C7 D+ W* m l4 v cout << "value= "<<value(postfix) << endl;
, d1 d( J: T) K: F: x }
$ T7 M2 l) m4 r2 Y, O' l, S9 n return 0;; L3 q/ ^* N5 T) v
} |