刚才发表了一篇后缀表达式求值(逆波兰表达式求值)的代码,虽然其在visual C++2010中编译出现了问题,不过幸好有好心人的热心帮助解决了。
那么为什么要用后缀表达式求值?根据我自己的理解,后缀表达式求值不必判断运算符的优先级,只要按顺序执行。每遇到一个操作符就处理一次,便于计算机处理。
那么下面我就分享一下我的中缀表达式转后缀的代码:
也许大家在考试时转化一定会:
中缀表达式:(8+9*10)-4/2+3
其转化思路:
1、将每个操作符对应的两个操作数用括号括上(((8+(9*10))-(4/2))+3)
2、将操作符移到对应的括号外(((8(910*)+)(42)/)-3)+
3、去掉括号即可 8910*+42/-3+
如果要用数据结构中的栈和队列实现
1、用一个字符串存储表达式
2、扫描字符串。当其为0--9时直接入队列,遇到左括号入栈,操作符级别 #:0用于最后判断,+ -:1,* /:2
3、首先向堆中放一个#,当进入堆的操作符的级别不小于栈顶操作符的优先级,则入栈,否则弹出栈顶元素并进入队列,将下一个操作符压入栈。
4、一直循环直到将所有字符处理完
5、最后将所有元素出队列并打印就可得到后缀表达式
1
#include<stdio.h>
2
#define Max 20
3
//自定义栈
4
template<class Elem>
5![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Stack
{
6
int top;
7
Elem *p;
8
int size;
9
};
10
template<class Elem>
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Set_Ssize(Stack<Elem> &sta,int n)
{
12
sta.size=n;
13
sta.p=new Elem[sta.size];
14
sta.top=0;
15
}
16
template<class Elem>
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Push(Stack<Elem> &sta,Elem item)
{
18
sta.p[sta.top++]=item;
19
}
20
template<class Elem>
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Pop(Stack<Elem> &sta,Elem &e)
{
22
e=sta.p[--sta.top];
23
}
24
template<class Elem>
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool IsEmpty(Stack<Elem> &sta)
{
26
return sta.top==0;
27
}
28
template<class Elem>
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool IsFull(Stack<Elem> &sta)
{
30
return sta.top==sta.size;
31
}
32
//自定义队列
33
template<class Elem>
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct MyQuene
{
35
int front;
36
int rear;
37
Elem *p;
38
int size;
39
};
40
template<class Elem>
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Set_Qsize(MyQuene<Elem> &Q,int n)
{
42
Q.size=n;
43
Q.front=0;
44
Q.rear=0;
45
Q.p=new Elem[Q.size];
46
}
47
template<class Elem>
48![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void AddQuene(MyQuene<Elem> &Q,Elem item)
{
49
Q.p[Q.rear++]=item;
50
if(Q.rear==Q.size)
51
Q.rear=0;
52
}
53
template<class Elem>
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void DeleteQuene(MyQuene<Elem> &Q,Elem& e)
{
55
e=Q.p[Q.front++];
56
if(Q.front==Q.size)
57
Q.front=0;
58
}
59
template<class Elem>
60![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
Elem GetTop(Stack<Elem> &sta)
{
61
return sta.p[sta.top-1];
62
}
63
template<class Elem>
64![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool IsEmpty(MyQuene<Elem> &Q)
{
65
return Q.front==Q.rear;
66
}
67
template<class Elem>
68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool IsFull(MyQuene<Elem> &Q)
{
69
int len=Q.front<Q.rear?Q.rear-Q.front:Q.rear-Q.front+Q.size;
70
return len==Q.size-1;
71
}
72
//定义运算符的优先级
73![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int GetPrecedence(char a)
{
74![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
switch(a)
{
75
case '#':return 0;
76
case '+':
77
case '-':return 1;
78
case '*':
79
case '/':return 2;
80
case '^':return 3;
81
default:break;
82
}
83
}
84
template<class Elem>
85![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Middle_Bhind(Stack<Elem> &st,MyQuene<Elem>&Mq,char*A,int n)
{//中缀表达式转为后缀表达式(自己的实验需求)
86
Set_Ssize(st,n);
87
Set_Qsize(Mq,n+1);
88
char tem;
89
int i=0;
90
Push(st,'#');
91![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
do
{
92
if((A[i]>='0'&&A[i]<='9')||(A[i]>='A'&&A[i]<='Z')||(A[i]>='a'&&A[i]<='z'))
93
AddQuene(Mq,A[i]);
94
else if(A[i]=='(')
95
Push(st,A[i]);
96![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else if(A[i]==')')
{
97![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(GetTop(st)!='(')
{
98
Pop(st,tem);
99
AddQuene(Mq,tem);
100
}
101
Pop(st,tem);
102
}
103
else if(GetTop(st)=='(')
104
Push(st,A[i]);
105![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
106![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(GetPrecedence(A[i])<=GetPrecedence(GetTop(st)))
{
107
Pop(st,tem);
108
AddQuene(Mq,tem);
109
}
110
Push(st,A[i]);
111
}
112
i++;
113
}while(A[i]!='\0');
114![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(GetTop(st)!='#')
{
115
Pop(st,tem);
116
AddQuene(Mq,tem);
117
}
118![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!IsEmpty(Mq))
{
119
DeleteQuene(Mq,tem);
120
printf("%c",tem);
121
}
122
putchar('\n');
123
}
124![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void main()
{
125
char str[Max];
126
Stack<char> st;
127
MyQuene<char>Mq;
128
printf("请输入中缀表达式:");
129
gets(str);
130
printf("后缀表达式:");
131
Middle_Bhind(st,Mq,str,Max);
132
}
133![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
134![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
135![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
136![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
137![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2011-01-19 15:51
あ维wêiセ 阅读(6004)
评论(5) 编辑 收藏 引用 所属分类:
C++