您的位置:首页 > 教程资讯 > 网络编程 > C语言 > C语言数据结构之栈:中缀表达式的计算

C语言数据结构之栈:中缀表达式的计算

发布于:2016-03-05 14:29:51   分享到:

*注:本人技术不咋的,就是拿代码出来和大家看看,代码漏洞百出,完全没有优化,主要看气质,是吧

 

学了数据结构——栈,当然少不了习题。习题中最难的也是最有意思的就是这个中缀表达式的计算了(可以算+-*/和^,当然也可以带小括号)。搞了很久很久啊,终于搞出来的。简单说一下程序原理:

因为中缀表达式基本没法算(就算可以也肯定会超时),所以得把中缀表达式转为后缀表达式。

程序分为两步

第一步:将中缀表达式转为后缀表达式

创建一个字符串,比如叫get,用于存储后缀表达式

先是输入一个字符串,逐一读取单个字符,当是数字则直接存入get,如果是操作符则:

创建栈,比如叫chas

while循环 当栈顶操作符优先级大于或等于当前操作符则弹出并把栈顶元素赋值给get 直到发现优先级小于当前操作符的栈顶的操作符,小于当前操作符的那个栈顶操作符不弹出 然后将当前操作符压入栈内

当当前操作符为'('则直接压入栈内

当当前操作符为')'则while循环 弹出栈顶操作符并赋值给get直到弹出的是'(' ( '('只弹出不赋值 ) 注意,')'不压入栈中

 

第二部:计算get

创建int型数组栈,比如ints

逐个读入get

当读到数字压入ints

当读到操作符则弹出两个ints的栈顶元素,并进行相应计算,将计算得到的值压入栈ints中

 

最后读完get时,ints数组只剩下一个元素了,输出。

 

自个儿写的稀巴烂源码(c):

  1 #include 
  2 #include <string.h>
  3 #include 
  4 
  5 int ints[10000];
  6 int intt;//ints的top 
  7 char chas[10000];
  8 int chat;//chas的top 
  9 int i=0, ii=1;
 10 char c;
 11 char get[10000];//输入的中缀表达式 
 12 char get2[10000];//计算得出的后缀表达式 
 13 
 14 void intpush(x)//整型栈压栈 
 15 {
 16     intt++;    ints[intt]=x;
 17 }
 18 void chapush(x)//字符型栈压栈 
 19 {
 20     chat++;    chas[chat]=x;
 21 }
 22 int intpop()//整型栈弹出 
 23 {
 24     intt--;    return ints[intt+1];
 25 }
 26 char chapop()//字符型栈弹出 
 27 {
 28     chat--;    return chas[chat+1];
 29 }
 30 void intadd(int x)//整型栈栈顶元素加入新的个位数字 
 31 {
 32     ints[intt]*=10;    ints[intt]+=x;
 33 }
 34 
 35 int find()//get2加入操作符 
 36 {
 37     c=chapop();
 38     get2[ii]=' ';
 39     get2[ii+1]=c;
 40     ii+=2;
 41     if(chat==0) return 0;
 42     return 1;
 43 }
 44 
 45 int main()
 46 {
 47     intt=0;    chat=0;
 48     gets(get);
 49     int lengets=strlen(get);
 50     for(i=0;i<=lengets-1;i++)//逐个读取输入的中缀表达式 
 51     {
 52         if (isdigit(get[i]))//当get[i]为数字时 
 53         {
 54             get2[ii]=get[i];
 55             ii++;
 56         }
 57         else
 58         {
 59             if(get[i]=='(')chapush('(');
 60             if(get[i]=='^')chapush('^');
 61             if(get[i]==')')
 62             {
 63                 c=chapop();
 64                 while(c!='(')
 65                 {
 66                     get2[ii]=' ';
 67                     get2[ii+1]=c;
 68                     ii+=2;
 69                     c=chapop();
 70                 }
 71             }
 72             if(get[i]=='+')
 73             {
 74                 while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 75                 {
 76                     if(find()==0)break;
 77                 }
 78                 chapush('+');
 79             }
 80             if(get[i]=='-')
 81             {
 82                 while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 83                 {
 84                     if(find()==0)break;
 85                 }
 86                 chapush('-');
 87             }
 88             if(get[i]=='*')
 89             {
 90                 while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 91                 {
 92                     if(find()==0)break;
 93                 }
 94                 chapush('*');
 95             }
 96             if(get[i]=='/')
 97             {
 98                 while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 99                 {
100                     if(find()==0)break;
101                 }
102                 chapush('/');
103             }
104             get2[ii]=' ';
105             ii++;
106         }
107         
108     }
109     while(chat>0)//输出栈内剩余的操作符 
110     {
111         int c=chapop();
112         get2[ii]=' ';
113         get2[ii+1]=c;
114         ii+=2;
115     }
116     get2[ii]='@';//加入结束符 
117     i=1;
118     while(get2[i]!='@')//当看到结束符停止计算 
119     {
120         if(get2[i]=='+'||get2[i]=='-'||get2[i]=='*'||get2[i]=='/'||get2[i]=='^')
121         {
122             int a=intpop();int b=intpop();int c;
123             if(get2[i]=='+') c=a+b;
124             if(get2[i]=='-') c=b-a;
125             if(get2[i]=='*') c=a*b;
126             if(get2[i]=='/') c=b/a;
127             if(get2[i]=='^') c=pow(b,a);
128             intpush(c);
129         }
130         else
131         {
132             if(get2[i]!=' ')
133             {
134                 intpush(get2[i]-48);
135                 ii=1;
136                 while(get2[i+ii]!=' ')
137                 {
138                     intadd(get2[i+ii]-48);
139                     ii++;
140                 }
141                 i+=ii-1;
142             }
143         }
144         i++;
145     }
146     printf("%d",ints[1]);
147     return 0;
148 }

 

样例输入:

1+(3+2)*(7^2+6*9)/(2)

 

样例输出:

258

 

好了,就写到这了。(原题:信息学奥赛一本通C++版 数据结构 栈 上机练习4 calc)//别问我为什么C++的书的练习我写的是C,我不会告诉你是因为那样文件名可以少打两个p

 

对了,再说一下,其实这玩意完全没必要写这么长,最NB办法:

右键桌面:新建文本文件

双击打开新建文本文件.txt,输入如下脚本:

@echo off
set /p get=
set /a ans=%get%
echo %ans%
pause
exit::可以不要这句exit

 

右键新建文本文件,重命名为:calc.bat

双击打开

样例输入:

1+(3+2)*(7*7+6*9)/(2)

 

样例输出:

258

 

除了乘方没法算,别的都一样

呵呵,我不想多什么了……


关于我们  加入我们  版权声明  商务合作  友情链接  网站地图  站长统计

脚本大全-脚本语言之家-版权所有 

Copyright (C) 2016 jiaoben.net, All Rights Reserved