*注:本人技术不咋的,就是拿代码出来和大家看看,代码漏洞百出,完全没有优化,主要看气质,是吧
学了数据结构——栈,当然少不了习题。习题中最难的也是最有意思的就是这个中缀表达式的计算了(可以算+-*/和^,当然也可以带小括号)。搞了很久很久啊,终于搞出来的。简单说一下程序原理:
因为中缀表达式基本没法算(就算可以也肯定会超时),所以得把中缀表达式转为后缀表达式。
程序分为两步
第一步:将中缀表达式转为后缀表达式
创建一个字符串,比如叫get,用于存储后缀表达式
先是输入一个字符串,逐一读取单个字符,当是数字则直接存入get,如果是操作符则:
创建栈,比如叫chas
while循环 当栈顶操作符优先级大于或等于当前操作符则弹出并把栈顶元素赋值给get 直到发现优先级小于当前操作符的栈顶的操作符,小于当前操作符的那个栈顶操作符不弹出 然后将当前操作符压入栈内
当当前操作符为'('则直接压入栈内
当当前操作符为')'则while循环 弹出栈顶操作符并赋值给get直到弹出的是'(' ( '('只弹出不赋值 ) 注意,')'不压入栈中
第二部:计算get
创建int型数组栈,比如ints
逐个读入get
当读到数字压入ints
当读到操作符则弹出两个ints的栈顶元素,并进行相应计算,将计算得到的值压入栈ints中
最后读完get时,ints数组只剩下一个元素了,输出。
自个儿写的稀巴烂源码(c):
1 #include <stdio.h>
2 #include <string.h>
3 #include <math.h>
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+69)/(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)(77+6*9)/(2)
样例输出:
258
除了乘方没法算,别的都一样
呵呵,我不想多什么了……
最新更新(2016/7/4):新代码,同样的功能,更快的速度,更短的代码
#include <stdio.h>
#include <string.h>
#include <math.h>
char ops[101];
int opsi=0;
int ovs[101];
int ovsi=0;
void opsin(char c)
{
opsi++;
ops[opsi]=c;
}
void ovsin(int num)
{
ovsi++;
ovs[ovsi]=num;
}
char opsout()
{
opsi--;
return ops[opsi+1];
}
int ovsout()
{
ovsi--;
return ovs[ovsi+1];
}
void count2(char c)
{
int b=ovsout();
int a=ovsout();
switch(c)
{
case '+':ovsin(a+b);break;
case '-':ovsin(a-b);break;
case '*':ovsin(a*b);break;
case '/':ovsin(a/b);break;
case '^':ovsin(pow(a,b));break;
}
}
int count(const char *str)
{
ops[0]=0;
int stri=0,lenstr=strlen(str);
while(stri<=lenstr-1)
{
if(str[stri]=='(')opsin('(');
else
if(str[stri]=='^')opsin('^');
else
if(str[stri]==')')
{
char c=opsout();
while(c!='(')
{
count2(c);
c=opsout();
}
}
else
if(str[stri]=='+')
{
while(ops[opsi]=='+'||ops[opsi]=='-'||ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
opsin('+');
}
else
if(str[stri]=='-')
{
while(ops[opsi]=='+'||ops[opsi]=='-'||ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
opsin('-');
}
else
if(str[stri]=='*')
{
while(ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
opsin('*');
}
else
if(str[stri]=='/')
{
while(ops[opsi]=='*'||ops[opsi]=='/'||ops[opsi]=='^')count2(opsout());
opsin('/');
}
else//num
{
if(stri>0)
{
if(str[stri-1]-48>=0&&str[stri-1]-48<=9)
ovsin(ovsout()*10+str[stri]-48);
else
ovsin(str[stri]-48);
}
else
ovsin(str[stri]-48);
}
stri++;
}
while(ovsi>1)count2(opsout());
return ovs[1];
}
int main()
{
char s[101];
gets(s);
printf("%d",count(s));
return 0;
}
原文链接: https://www.cnblogs.com/rjgcs/p/5195686.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/228844
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!