代入以下代码,得:11,9,4,2,1,6 滑稽~
. D4 @& o; [5 ?; W0 \" {( O2 ~; v6 l1 Y. @2 J& ^% f: A
#include <iostream>
" I" }% i1 U# A6 C1 Y#include <string.h>: m& T( N& ~! b$ j4 k
using namespace std;
( j" I. J; N, K$ ?# i6 c j( Z5 atemplate <class T># h, h. E9 W/ B
class Node M) E& Y" @% K5 x7 W
{
9 y% m3 R+ g, q# Q& rpublic:
1 S! Z; l* s% C, V- ~4 A, w# Z T data;
8 w( p0 f4 J8 B& M X1 Q. @3 s( L Node<T> *next;' q! T! ?( }; b
Node(); x) l- G# M6 Y$ x! Y
{. _: V6 R6 A) U' m3 q& H/ |
this->next = NULL;
' V( n- Z( ] k% I/ A8 _2 t }5 D" _% j7 U& H9 j7 z! P
Node(T data,Node<T> *next=NULL)
5 B+ Y! Z- R4 y1 W, F+ Z9 s# H {
/ S9 a# J7 A8 o, B y this->data = data;
% y+ {) |6 d; S$ x6 K. {4 q this->next = next;2 Q$ S# d6 q2 C; C
}
! c7 c& E, r5 a' e8 D! C" P/ q" R};, U5 ^, u3 M: \: j
5 T) ~8 [. |* M
template <class T>! a+ ^* |0 T' N; H* y
class LinkedStack
$ C! j* t0 u( z0 v{
% M; k5 k& p8 j5 aprivate:0 g0 s0 [5 U3 [/ R! n
Node<T> *top;
/ k" G7 A2 O3 i$ `+ H! gpublic:
, [) M4 q0 l0 Q LinkedStack();6 |& M3 N; ^6 q6 F' L% P& D
~LinkedStack();
1 l+ j, y S+ D3 h' T bool isEmpty();
) {! f/ P3 H! b8 @ void push(T x);5 i" Y7 _; F4 V4 N0 H
T pop();4 _, A) d$ L8 D* g- w
T get();
) D# ?5 F3 X0 D1 k' N2 E. W1 G};2 V4 h* f" s! r- c1 n) d% m
2 _/ M) F6 b6 M
template <class T>
8 o r J6 A* j7 I: S4 nLinkedStack<T>::LinkedStack()) B" C0 o3 o* b* K
{
4 R. h S1 ~" h* E6 B5 o7 Y top = NULL;( [$ N; C4 Y/ n: F
}. U- G. [: o/ P e" f
% |9 H1 i4 m. r* w J2 f3 [ b
template <class T>. K7 D" U0 m9 u
LinkedStack<T>::~LinkedStack()7 N4 x' z- F0 u& P8 F4 x, P
{* N, X2 {- l9 @ o4 |; m
Node<T> *p = top;# S+ U% [% s9 x6 P; i
Node<T> *q;
+ G. t2 \1 L8 Q while(p!=top)
3 Y" d/ V0 Z' U( L1 U a {0 Q+ v$ g) y2 f' _3 L7 X a/ c6 D
q = p;
@' F/ {+ m; l4 S- @( x9 p p = p->next;! z$ A- ?! g0 j& T7 _
delete p;- u1 Q1 D7 F( X/ i
}1 ]( F4 S; d, P" n( a% [: L
top = NULL;. @5 o( E7 E! r: l# g" V0 Q
}
. r3 _( H9 p' E4 {0 S
( ^% ?- B+ I: N' t; ytemplate <class T>
" G' q; J4 `6 g& qbool LinkedStack<T>::isEmpty()
. j% m& `+ t& J. T" L{
- A6 f9 B% e9 |2 a( Q" D return top == NULL;2 \- w! W, u! y: i- P' U: Q
}* V& T0 b+ B; S: u1 Q# z2 l( t* ^8 N0 G
" l8 ` H G9 i# n0 dtemplate <class T>6 J* F7 S. e3 N
void LinkedStack<T>::push(T x)# Y5 f9 l* a4 O4 m! X
{
+ j4 I& r6 e/ _" m) C top = new Node<T>(x,top);
( ]! ]& j) ^- f6 Z6 Y$ z, S}
3 T/ E" i; D3 N) [; o- |% x. k
6 X, U" ]) A% S4 q3 b) p5 Z7 H" stemplate <class T>& Q/ v b! k1 N
T LinkedStack<T>::pop()7 m0 k2 A4 l* E# c/ O$ V' ]. m: ~
{; N' U9 Q) g5 V: W& a
if(!isEmpty())
. _; C+ L8 G! l2 r+ l' R {
( _# ~8 _, j4 v6 G2 y0 C T x = top->data;
; n7 y* z+ w/ Y2 t+ k5 j8 V. b+ O6 A Node<T> *p = top;8 I; P7 D2 r1 U3 A, p
top = top->next;
5 K! X- \; @# ]; n% b5 o delete p;
# z6 o' D2 ^: m8 k) B, B4 m return x;
" Q. l; o' ~3 x+ J% r- a( c( v }, f& K% V I0 E; a
throw "空栈,不能执行出栈操作";; W" h% c# V- c6 K- S
}! n5 a* ` B& t1 ` Y
; c! d+ |& D, G( c
template <class T>6 \9 g8 t8 a! O- s! p
T LinkedStack<T>::get()
! x# Z6 \2 Q+ I6 K! z{; Y. ?7 g. Z% H# Z+ o6 w) K9 R
if(!isEmpty())
9 u3 z& K4 H ?4 e3 A {
$ t+ ]) @ I# R5 l7 l! H1 H return top->data;
! A# D! e2 j W! h k X, T1 D+ h }1 L: ]% c# Z# T! ?( \& Y
throw "空栈,不能获得栈顶元素";
% q" N/ t6 l5 _# g}
% W" H0 e( h) I1 |
$ {2 e5 o1 J# @8 dchar * toPostfix(char *expstr)6 s* ^- V+ O4 |5 w% H
{9 U2 \3 q1 p7 l% M
LinkedStack<char> stack;
1 _1 S$ f+ ], M- w; F char *postfix = new char[strlen(expstr)*2];
4 K9 L$ g: G& Q9 G; C2 o! O2 `" R int i=0;$ f4 q. B, {8 e' `2 z' r
int j=0;' n* f ]* d2 P7 l2 V# R
char out ;! |0 [( k% `0 [; F) L5 E
while(expstr[i]!='\0')
z0 ^) \8 w$ f' R* F y/ Z {5 C: ^ y: @& m/ ^# b3 @+ x' y
switch(expstr[i]), `5 x) y4 ?5 _. f/ S
{& Y2 O3 A7 S. b M
case'+':8 f8 X2 {! L2 C- H3 r1 K" j
case'-':! x0 \ m, A; g
while(!stack.isEmpty()&&stack.get()!='(')
3 {( g( X: u4 L3 M2 N7 E {
: P8 x) P" \# l postfix[j++] = stack.pop();+ ]8 k; e6 t. L1 A& p3 A3 L: r
}
+ e v; `% m# p6 ~; g. S stack.push(expstr[i++]);" h8 w3 l- l1 H; W+ ]2 f
break;
6 |2 V- M7 r% A2 ~ case'*':
0 g k9 N0 `: W9 k case'/':
3 a# ~. Z! }& i9 P while(!stack.isEmpty()&&(stack.get()=='*'||stack.get()=='/'))
" l8 M. H: s8 e4 z5 j {9 T) b8 Z' j& R3 p C: F8 k
postfix[j++] = stack.pop();$ T$ x+ p4 S# @6 i0 |& @ [1 X' @
}
. h- ? |0 D2 K" [2 s7 d" i stack.push(expstr[i++]);' D" h) m; v; ]
break;' R! d/ `8 y9 T* r
case'(':stack.push(expstr[i++]);
; h) B, d9 C0 x break;
9 {. R" Z# B" J7 t case')':out = stack.pop();7 W: F& O; ]4 \/ \
while(!stack.isEmpty()&&out!='(')
2 c9 x2 w/ P' _+ L, R5 T {: \6 O7 r/ ] r5 J7 a v
postfix[j++] = out;
: j, n- v; G# h/ R: x8 L) `2 f+ p out = stack.pop();' q& B( s) |5 E# K& t+ J) ^5 }6 S. S
}
" {/ X2 Y" z/ S6 S7 A1 n4 ] D; r i++;
5 [5 C) f. `, K) F break;
5 r% h! @( q, O' E default:2 d# D# l4 o. z$ b9 F9 n4 J1 V
while(expstr[i]>='0'&&expstr[i]<='9'&&expstr[i]!='\0')
N! d% R- a) R9 e6 k' a {& \& ~6 s7 r- V) t
postfix[j++] = expstr[i++];
4 D. o7 f" _$ _4 x6 N0 J5 k }7 X! I$ h/ j* ?8 O" `% s
postfix[j++]=' ';
; R% q4 t4 b) R break;8 D' U+ w9 P* m3 j* ~
}
( e2 {! d0 j4 G# ]4 M+ |& g }
8 `: u/ o" O, D) {$ I7 d: P while(!stack.isEmpty()), L: C3 ^5 z5 x/ Y8 l2 x0 E: I/ ?
{
; E0 W3 |" g: f- O- B postfix[j++]=stack.pop();& K" t: M, e4 [' f* V S' u6 ?
}
, U1 H/ z& q- l o' D8 G: ^ postfix[j]='\0';
% e6 @- H6 e+ J3 p. ] return postfix;+ M4 T, r6 ^/ L( e1 U
}' s8 b# k1 v, N- p
8 g& r r8 w7 x4 _# F7 C1 Q* aint value(char *postfix)
: J3 I' K- F# R/ m' r{! x/ C- E# z: N
LinkedStack<int> stack;
$ T! M9 t, s' C& {" P int i=0;
9 _, h* D" c1 n# E) S8 D int result = 0;
, B% R& H5 R1 _8 r while(postfix[i]!='\0')* R' a( c. u, p& w$ H" s4 k
{
- Q# _# J% C% q) D- x$ J if(postfix[i]>='0'&&postfix[i]<='9')
/ Q2 {+ p, S5 c+ K {
0 `1 A' y7 D! o% O0 o result = 0;
. Q+ c! `: K5 k! F2 T& X3 g/ n+ m while(postfix[i]!=' ')
& A: ]+ ~: m# o: N% @1 l {& Z9 A/ p: r& K8 |
result = result*10+postfix[i++]-'0';
! x; g! @: y4 p0 q. a4 [ }
% t; |5 u; r- |" v1 t+ S' @0 u i++;
, |1 e5 U1 D$ f, f/ { stack.push(result);2 ~) q9 m4 P0 H/ ~: z) S" X
}( z' \; v) c2 ]4 @& T
else
( i8 ^6 F/ R1 O6 j7 Q* w {) S0 Z' g7 f* ~) y$ E
if(postfix[i]!=' ')
& @6 l$ A% a* c" Z, r" I7 w {
) H, Q! V5 A w" S( V% q6 ]0 ` int y = stack.pop();1 `( P; q! L2 |
int x = stack.pop();
% v) {; t$ e! Z5 r switch(postfix[i])
# Y! g4 Z. C* m' b% Q; H# _ {
$ x% M' j7 ^0 L* A1 S+ {3 }( G case'+':result = x + y;
4 d% y5 n1 t: R! S break;
2 P( x3 e/ }7 \ H case'-':result = x - y;- N, e; L2 x7 N
break;% P$ [9 c3 A/ l+ o) [* M
case'*':result = x *y;; k6 M. E( [+ ]/ P1 c
break;
. O! R$ o! v* p- H8 N2 V9 y0 V case'/':result = x / y;# W# Q% @* s6 z' _ U6 i1 P( @
break;4 P5 @) X I& N4 b! `7 v1 W
}) f' r; Y5 R0 C: }7 Z5 K
stack.push(result);% l9 M: K1 S+ ?
}' v* ?& s' w7 S: J
i++;! l" a# @/ t9 [ s& S
}
" T# Z. h" h" j2 }$ o/ E }
3 n& A, z* w/ o% [( c. i return stack.pop();
! S1 S5 \( j5 j6 o* C6 w6 B}
- s2 f1 {$ T. w. T0 Z9 M& C6 M& _- ^3 R: ?
int main() @3 }4 {; Y; Q% h3 z' V' h
{# S5 M1 _# h1 ~8 ]
//char *expstr = "121+10*(52-49+20)/((35-25)*2+10)";
4 p& s$ H" J2 A5 v! V( C; b& H* S, _7 n cout << "请输入表达式:";0 r1 x$ u1 d8 V
//char *a ;
p; i% w: w( D% { //cin >> *a;
8 F; A7 [0 Z% a3 M9 ?8 c- C char expstr[20]={0};: f- T5 O' W% o: r
while(1)( E$ m6 P+ ]: q$ m
{6 F! R( @& m" S" w' {4 A
cin>>expstr;' ]; Z; `( z% }
char *postfix = toPostfix(expstr);( ] V! r% E9 m$ Z0 m" \
cout << "expstr= "<<expstr << endl;( S) t' M& ~4 u% b6 J
cout << "postfix= "<<postfix<<endl;
: o; j% @3 j) n7 p5 y cout << "value= "<<value(postfix) << endl;
/ K" V" O7 q5 H& a2 [5 Z0 W }4 O5 ~( U0 L5 [/ C0 w( h" a8 w# _
return 0;
8 ]. c6 u7 e7 y} |