posts - 6,  comments - 30,  trackbacks - 0
刚才发表了一篇后缀表达式求值(逆波兰表达式求值)的代码,虽然其在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//自定义栈
  4template<class Elem>
  5struct Stack{
  6    int top;
  7    Elem *p;
  8    int size;
  9}
;
 10template<class Elem>
 11void Set_Ssize(Stack<Elem> &sta,int n){
 12    sta.size=n;
 13    sta.p=new Elem[sta.size];
 14    sta.top=0;
 15}

 16template<class Elem>
 17void Push(Stack<Elem> &sta,Elem item){
 18    sta.p[sta.top++]=item;
 19}

 20template<class Elem>
 21void Pop(Stack<Elem> &sta,Elem &e){
 22    e=sta.p[--sta.top];
 23}

 24template<class Elem>
 25bool IsEmpty(Stack<Elem> &sta){
 26    return sta.top==0;
 27}

 28template<class Elem>
 29bool IsFull(Stack<Elem> &sta){
 30    return sta.top==sta.size;
 31}

 32//自定义队列
 33template<class Elem>
 34struct MyQuene{
 35    int front;
 36    int rear;
 37    Elem *p;
 38    int size;
 39}
;
 40template<class Elem>
 41void 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}
    
 47template<class Elem>
 48void AddQuene(MyQuene<Elem> &Q,Elem item){
 49    Q.p[Q.rear++]=item;
 50    if(Q.rear==Q.size)
 51        Q.rear=0;
 52}

 53template<class Elem>
 54void DeleteQuene(MyQuene<Elem> &Q,Elem& e){
 55    e=Q.p[Q.front++];
 56    if(Q.front==Q.size)
 57        Q.front=0;
 58}

 59template<class Elem>
 60Elem GetTop(Stack<Elem> &sta){
 61    return sta.p[sta.top-1];
 62}

 63template<class Elem>
 64bool IsEmpty(MyQuene<Elem> &Q){
 65    return Q.front==Q.rear;
 66}

 67template<class Elem>
 68bool 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//定义运算符的优先级
 73int GetPrecedence(char a){
 74    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}

 84template<class Elem>
 85void 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    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        else if(A[i]==')'){
 97            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        else{
106            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    while(GetTop(st)!='#'){
115        Pop(st,tem);
116        AddQuene(Mq,tem);
117    }

118    while(!IsEmpty(Mq)){
119        DeleteQuene(Mq,tem);
120        printf("%c",tem);
121    }

122    putchar('\n');
123}

124void 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
134
135
136
137


posted on 2011-01-19 15:51 あ维wêiセ 阅读(5986) 评论(5)  编辑 收藏 引用 所属分类: C++

FeedBack:
# re: 中缀表达式转为后缀表达式
2011-01-26 16:39 | jhayumu
你的队列模板中,比如说size =5的话,只能有4个位子可用。。。  回复  更多评论
  
# re: 中缀表达式转为后缀表达式
2011-01-27 17:34 | あ维wêiセ
@jhayumu
恩啊,由于要实现循环队列,防止“假溢”现象,以区别队空与队满  回复  更多评论
  
# re: 中缀表达式转为后缀表达式
2012-08-24 23:11 | js
(8+9*10)-4/2+3

(8+91*0)-4/2+3

怎么区分?  回复  更多评论
  
# re: 中缀表达式转为后缀表达式
2012-08-25 08:47 | yangwei
是的,要牺牲一个来区分队空和队满@jhayumu
  回复  更多评论
  
# re: 中缀表达式转为后缀表达式
2012-08-25 08:55 | yangwei
你可以考虑先将表达式中的数字字符转换成对应的数字,成为一个元素,那么打印时加空格就好@js
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜