#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MaxSize 99
char calc[MaxSize],expr[MaxSize]
int i,t
struct
{
char data[MaxSize]
int top
}Sym
struct
{
double data[MaxSize]
int top
}Num
double ston(char x[],int *p)
{
int j=*p+1,i
double n=0
char sign=x[*p]
if(sign=='+'||sign=='-') *p=*p+1
while(x[j]>='0'&&x[j]<='9')
{
j++
}
for(i=*pi<ji++)
{
n=n*10+(x[i]-'0')
}
if(x[j]=='.')
{
*p=++j
while(x[j]>='0'&&x[j]<='9')
{
j++
}
for(i=*pi<ji++)
{
n=n+pow(0.1,i-*p+1)*(x[i]-'0')
}
}
*p=j
if(sign=='-') return(-n)
return(n)
}
void InitStack()
{
Sym.top=Num.top=-1
}
void SymPush()
{
if(Sym.top<MaxSize-1)
{
Sym.data[++Sym.top]=calc[i++]
}
else
{
printf("Sym栈满\n")
return
}
}
void SymPop()
{
if(Sym.top>=0)
{
expr[++t]=Sym.data[Sym.top--]
}
else
{
printf("Sym栈空\n")
return
}
}
void NumPush()
{
if(Num.top<MaxSize-1)
{
Num.data[++Num.top]=ston(expr,&i)
}
else
{
printf("Num栈满\n")
return
}
}
void NumPop()
{
if(Num.top>=0)
{
if(expr[i]!=' ')
{
switch(expr[i])
{
case '+':Num.data[Num.top-1]=Num.data[Num.top-1]+Num.data[Num.top]break
case '-':Num.data[Num.top-1]=Num.data[Num.top-1]-Num.data[Num.top]break
case '*':Num.data[Num.top-1]=Num.data[Num.top-1]*Num.data[Num.top]break
case '/':Num.data[Num.top-1]=Num.data[Num.top-1]/Num.data[Num.top]break
case '^':Num.data[Num.top-1]=pow(Num.data[Num.top-1],Num.data[Num.top])break
}
Num.top--
}
}
else
{
printf("Num栈空\n")
return
}
}
int main(void)
{
loop1:
i=0,t=-1
system("cls")
printf("中缀表达式：")
InitStack(),gets(calc)
while(calc[i]!='\0'&&calc[i]!='=')
{
if(calc[i]>='0'&&calc[i]<='9')
{
while((calc[i]>='0'&&calc[i]<='9')||(calc[i]=='.'))
{
loop2:
expr[++t]=calc[i++]
}
expr[++t]=' '
}
else if(calc[i]=='(')
{
SymPush()
}
else if(calc[i]==')')
{
while(Sym.data[Sym.top]!='(')
{
SymPop()
expr[++t]=' '
}
Sym.data[Sym.top--]='\0'
i++
}
else if((calc[i]=='+'||calc[i]=='-'))
{
if((i==0)||(!(calc[i-1]>='0'&&calc[i-1]<='9')&&calc[i-1]!=')')) goto loop2
while(Sym.top>=0&&Sym.data[Sym.top]!='(')
{
SymPop()
expr[++t]=' '
}
SymPush()
}
else if(calc[i]=='*'||calc[i]=='/')
{
while(Sym.top>=0&&(Sym.data[Sym.top]=='*'||Sym.data[Sym.top]=='/'||Sym.data[Sym.top]=='^'))
{
SymPop()
expr[++t]=' '
}
SymPush()
}
else if(calc[i]=='^')
{
while(Sym.top>=0&&Sym.data[Sym.top]=='^')
{
SymPop()
expr[++t]=' '
}
SymPush()
}
else
{
i++
}
}
while(Sym.top>=0)
{
SymPop()
expr[++t]=' '
}
expr[++t]=Sym.data[++Sym.top]='\0'
printf("后缀表达式：%s\n",expr)
for(i=0expr[i]!='\0'i++)
{
if((expr[i]>='0'&&expr[i]<='9')||((expr[i]=='+'||expr[i]=='-')&&(expr[i+1]>='0'&&expr[i+1]<='9')))
{
NumPush()
}
else
{
NumPop()
}
}
printf("运算结果为：%g\n",Num.data[0])
printf("Continue(y/n)?")
switch(getch())
{
case 'y':{system("cls")goto loop1}
case 'n':
default :exit(0)
}
getch()
return(0)
}
后缀表达式是一种十分有用的表达式，它将中缀表达式转换为可以依靠简单的 *** 作就能得到运算结果的表达式。例如，(a+b)*(c+d)转换为a,b,+,c,d,+,*。
它的优势在于只用两种简单的 *** 作，入栈和出栈就可以解决任何中缀表达式的运算。其运算方式为：如果当前字符为数字或变量，则压入栈内；如果是运算符，则将栈顶两个元素d出栈外并作相应运算，再将结果压入栈内。当后缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。
中缀表达式--->后缀表达式
a+b --->a,b,+
a+(b-c) --->a,b,c,-,+
a+(b-c)*d --->a,b,c,-,d,*,+
a=1+3 --->a=1,3,+
将中缀表达式转换为后缀表达式的一般算法是：
[1] 首先构造一个运算符栈(也可放置括号)，运算符(以括号分界点)在栈内遵循越往栈顶优先级越高的原则。
[2] 从左至右扫描中缀表达式，从左边第一个字符开始判断：
[2.1] 如果当前字符是数字，则分析到数字串的结尾并将数字串直接输出。
[2.2] 如果是运算符，则比较优先级。如果当前运算符的优先级比栈顶运算符的优先级更高(当栈顶是括号时，直接入栈)，则将运算符直接入栈；否则将栈顶运算符出栈并输出，直到当前运算符的优先级比栈顶运算符的优先级更高(当栈顶是括号时，直接入栈)，再将当前运算符入栈。
[2.3] 如果是括号，则根据括号的方向进行处理。如果是左括号，则直接入栈；否则，遇左括号前将所有的运算符全部出栈并输出，遇左括号后将右左的两括号一起删除。
[3] 重复上述 *** 作[2]直至扫描结束，将栈内剩余运算符全部出栈并输出。中缀表达式也就转换为后缀表达式了。
各运算符及符号优先级：
)：遇(前，将运算符全部出栈并输出；遇(后，将两括号一起删除
(：直接入栈
+、-：1
*、/、%：2
^：3
第二种方法：
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
double fun1()
double fun2()
double fun3()
double fun4()
double fun5()
char calc[64]
int n
double fun1()
{
double t
t=fun2()
while((calc[n]=='+')||(calc[n]=='-'))
{
switch(calc[n])
{
case '+':n++,t=t+fun2()break
case '-':n++,t=t-fun2()break
}
}
return(t)
}
double fun2()
{
double t
t=fun3()
while((calc[n]=='*')||(calc[n]=='/'))
{
switch(calc[n])
{
case '*':n++,t=t*fun3()break
case '/':n++,t=t/fun3()break
}
}
return(t)
}
double fun3()
{
double t
t=fun4()
while(calc[n]=='^')
{
n++,t=pow(t,fun4())
}
return(t)
}
double fun4()
{
char num[16]
int i=0
double t
if(calc[n]=='(')
{
n++,t=fun1(),n++
}
else if(fun5())
{
while(fun5())
{
num[i++]=calc[n++]
}
num[i]='\0'
t=atof(num)
}
return(t)
}
double fun5()
{
if(((calc[n]>='0'&&calc[n]<='9')||(calc[n]=='.'))||(n>0&&(calc[n-1]=='+'||calc[n-1]=='-'||calc[n-1]=='*'||calc[n-1]=='/'||calc[n-1]=='^')))
return(1)
else
return(0)
}
int main(void)
{
loop1:
n=0
printf("Input a calculation method like 1+2^(3-4)*5/10=↙\nPlease:")
gets(calc)
printf("Result=%g\n",fun1())
printf("Continue(y/n)?")
switch(getch())
{
case 'y':{system("cls")goto loop1}
case 'n':
default :exit(0)
}
getch()
return(0)
}
/**************************************************************//* 基于基本遗传算法的函数最优化 */
/* 同济大学计算机系 王小平 2000年5月 */
/**************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
#include<time.h>
#include<string.h>
#include "graph.c"
#include "operator.c"
#define POP_SIZE 25 /* 种群大小 */
#define G_LENGTH 8 /* 染色体长度 */
#define C_RATE 0.2 /* 交叉概率*/
#define M_RATE 0.01/* 变异概率 */
#define XMAX 255 /* 函数变量最大值 */
#define X1 350 /* 函数图形区窗口左上点X坐标 */
#define Y1 40 /* 函数图形区窗口左上点Y坐标 */
#define XR1 255 /* 函数图形区窗口长度 */
#define YR1 200 /* 函数图形区窗口高度 */
#define X2 360 /* 适应度图形区窗口左上点X坐标 */
#define Y2 280 /* 适应度图形区窗口左上点Y坐标 */
#define XR2 250 /* 适应度图形区窗口长度 */
#define YR2 100 /* 适应度图形区窗口宽度 */
#define STEP 2 /* 适应度图形区X方向步长 */
void initialize_gene(gene,pop_size,g_length)
/* 种群中个体遗传基因型的初始化 */
unsigned char *gene /* 遗传基因 */
int pop_size /* 种群大小 */
int g_length /* 个体染色体长度 */
{
int i,j
randomize()
for(i=0i<pop_sizei++)
for(j=0j<g_lengthj++)
*(gene+i*g_length+j)=random(2)
}
int gene_to_pheno(gene,g_length)
/* 基因型到表现型的变换--解码 */
unsigned char *gene /* 基因型 */
int g_length/* 染色体长度 */
{
int i,pheno
pheno=0
for(i=0i<g_lengthi++)
pheno=pheno*2+*(gene+i)
return(pheno)
}
void calc_fitness(gene,fitness,pop_size,g_length,func, max_fit,avg_fit)
/* 计算种群中个体的适应度 */
unsigned char *gene /* 个体的遗传基因 */
double *fitness /* 个体的适应度 */
double *func /* 评价函数 */
double *max_fit,*avg_fit /* 最大适应度与平均适应度 */
int pop_size /* 种群大小 */
int g_length /* 个体染色体长度 */
{
unsigned char *g /* 个体的遗传基因指针变量 */
int pheno/* 个体的表现型 */
int i,j
double f
*max_fit=0.0
*avg_fit=0.0
f=(double)pop_size
for(i=0i<pop_sizei++)
{
g=gene+i*g_length
pheno=gene_to_pheno(g,g_length)
*(fitness+i)=*(func+pheno)
if(*(fitness+i)>*max_fit)
*max_fit=*(fitness+i)
*avg_fit=*avg_fit+*(fitness+i)/f
}
}
void sga_reproduction(gene,fitness,new_gene,new_fitness,pop_size,g_length)
/* 基于个体的适应度评价进行新一代个体的选择(轮盘赌方法)，选择后分别将新的基因型和适应度代入到新个体中 */
unsigned char *gene /* 当前代的个体遗传基因型 */
unsigned char *new_gene /* 新一代的个体遗传基因型 */
double *fitness /* 当前代的个体适应度 */
double *new_fitness /* 新一代的个体适应度 */
int pop_size /* 种群大小 */
int g_length /* 染色体长度 */
{
double sum_of_fitness
double border
double r/* 轮盘上的选择位置变量 */
int i,j
int num
sum_of_fitness=0.0
for(i=0i<pop_sizei++) /* 轮盘赌的选择循环 */
sum_of_fitness=sum_of_fitness+*(fitness+i)
for(i=0i<pop_sizei++)
{
r=sum_of_fitness*(random(10001)/10000.0)
num=0
border=*fitness
while(border<r)
{
num++
border=border+*(fitness+num)
}
for(j=0j<g_lengthj++)
*(new_gene+i*g_length+j)=*(gene+num*g_length+j)
*(new_fitness+i)=*(fitness+num)
}
}
void sga_crossover(gene,pop_size,g_length,c_rate)
/* 基本遗传算法的交叉 *** 作--单点交叉 */
unsigned char *gene /* 遗传基因 */
int pop_size /* 种群大小 */
int g_length /* 个体染色体长度 */
double c_rate /* 交叉概率 */
{
unsigned char *gene1 /* 父个体1的遗传基因指针变量 */
unsigned char *gene2 /* 父个体1的遗传基因指针变量 */
unsigned char work /* 中间变量 */
int i,j
int c_pos /* 交叉位置变量 */
double r /* 随机数变量 */
for(i=0i<pop_size-1i=i+2)
{
r=random(10001)/10000.0
if(r<=c_rate)
{
gene1=gene+g_length*i
gene2=gene1+g_length
c_pos=random(g_length-2)+1
for(j=c_posj<g_lengthj++) /* 两个父个体之间部分遗传基因的交换 */
{ work=*(gene1+j)
*(gene1+j)=*(gene2+j)
*(gene2+j)=work
}
}
}
}
void sga_mutation(gene,pop_size,g_length,m_rate)
/* 基本遗传算法的变异 *** 作--个体遗传基因按小概率翻转 */
unsigned char *gene /* 遗传基因 */
int pop_size /* 种群大小 */
int g_length /* 染色体长度 */
double m_rate/* 变异概率 */
{
int i,j
double r
for(i=0i<pop_sizei++)
{
for(j=0j<g_lengthj++)
r=random(10001)/10000.0
if(r<=m_rate) /* 变异发生判断 */
{
if ( *(gene+g_length*i+j)==0)
*(gene+g_length*i+j)=1
else
*(gene+g_length*i+j)=0
}
}
}
void make_function(func,xmax)
/* 生成一个函数, 用于最优化计算的目标函数(最大化) */
/* f=∑ai*sin(x* bi+ci) 其中 ai∈[0, 0.35]的均匀随机数
bi∈[2*pi, 5*2*pi] /xmax的均匀随机数
ci∈[0, 2*pi]的均匀随机数
x∈[0,xmax]为优化变量
i=1,2,3 */
double *func /* 函数值 */
int xmax /* 变量最大值 <XMAX */
{
int x,i
double a[3],b[3],c[3]
double pi=3.141592
double fxmax,fx,f_value
double f_min,f_max,f_mid,f_range
double dbl
randomize()
fxmax=(double)xmax
for(i=0i<3i++) /* 优化函数为三个三角函数之和 */
{
a[i]=0.35*(random(10001)/10000.0)
b[i]=(4*(random(10001)/10000.0)+1)*2.0*pi/fxmax
c[i]=2.0*pi*(random(10001)/10000.0)
}
f_min=1.0
f_max=0.0
for(x=0x<=xmaxx++) /* 将优化函数正规化为[0,1]区间数 */
{
fx=(double)x
f_value=0.0
for(i=0i<3i++)
{
dbl=b[i]*fx+c[i]
f_value=f_value+a[i]*sin(dbl)
}
f_value=f_value+0.5
if(f_value>f_max) f_max=f_value
if(f_value<f_min) f_min=f_value
*(func+x)=(double)f_value
}
f_range=f_max-f_min
f_mid=(f_max+f_min)/2.0
for(x=0x<=xmaxx++)
{
f_value=(*(func+x)-f_mid)/f_range+0.5
if(f_value>1.0) f_value=1.0
else if(f_value<0.0) f_value=0.0
*(func+x)=f_value
}
}
void g_draw_func(func,xmax)
/* 绘制优化函数的图形 */
double *func/* 函数值 */
int xmax /* 变量最大值 */
{
int x,y,x_old,y_old,i
double f
g_rectangle(X1+1,Y1+1,X1+XR1-1,Y1+YR1-1,0,1)
g_rectangle(X1+1,Y1-12,X1+XR1,Y1-1,8,1)
g_rectangle(X1,Y1,X1+XR1,Y1+YR1,6,0)
x_old=X1
y_old=Y1+YR1-(int)(*func*YR1)
f=XR1/(double)xmax
for(i=1i<=xmaxi++)
{
x=X1+(int)(i*f)
y=Y1+YR1-(int)(*(func+i)*YR1)
g_line(x_old,y_old,x,y,12)
x_old=x
y_old=y
}
}
void g_init_grph(func,xmax)
/* 初始化画面的图形 */
double *func /* 函数值 */
int xmax /* 变量最大值 */
{
int x,y,x_old,y_old,i
char c[5]
/*初始化函数图形区*/
g_rectangle(320,0,639,399,8,1)
g_rectangle(321,1,638,16,8,1)
disp_hz16("基于基本遗传算法的函数最优化",370,1,15)
disp_hz16("g(x)",X1-30,Y1-18,15)
disp_hz16("1.0",X1-30,Y1,15)
disp_hz16("0",X1-10,Y1+YR1,15)
disp_hz16("x",X1+XR1+10,Y1+YR1-20,15)
disp_hz16("XMAX",X1+XR1-10,Y1+YR1,15)
g_draw_func(func,xmax)
/* 初始化适应度图形区 */
g_rectangle(X2,Y2,X2+XR2,Y2+YR2,0,1)
g_rectangle(X2,Y2,X2+XR2,Y2+YR2,6,0)
setcolor(15)
disp_hz16("最大适应度",X2+5,Y2-18,15)
g_line(X2+90,Y2-10,X2+110,Y2-10,11)
setcolor(15)
disp_hz16("平均适应度",X2+120,Y2-18,15)
g_line(X2+205,Y2-10,X2+225,Y2-10,9)
setcolor(15)
disp_hz16("世代数",X2+168,Y2+YR2+10,15)
g_text(X2-30,Y2,15,"1.0")
/* g_text(X2-30,Y2+YR2,15,"0.0")*/
}
void g_plot_grph(num,gene,fitness,pop_size,g_length,func, xmax,max_fit,m_f_old,avg_fit,a_f_old,gen_num)
/* 随世代进化更新图形 */
unsigned char *gene /* 遗传基因 */
double *fitness /* 适应度 */
double *func /* 函数值 */
double max_fit,m_f_old /* 当前代最大适应度，上一代最大适应度 */
double avg_fit,a_f_old /* 当前代平均适应度，上一代平均适应度 */
int num /* 当前世代数 */
int pop_size /* 种群大小 */
int g_length /* 染色体长度 */
int xmax /* 变量最大值 */
int gen_num /* 最大世代数 */
{
int i,j,x,y,x_old,y_old
double f
unsigned char *g
char c[10]
/* 显示当前世代种群中个体的遗传基因 */
if(num==gen_num-1)
{
for(i=0i<pop_sizei++)
{
printf("Indv.%2d:",i+1)
for(j=0j<g_lengthj++)
printf("%d",*(gene+i*g_length+j))
printf("==>Fitness %.4f\n",*(fitness+i))
}
printf("Max_fit=%f \n",max_fit)
printf("Avg_fit=%f \n",avg_fit)
}
/* 显示个体在函数图形区中的位置 */
g_draw_func(func,xmax)
f=XR1/(double)xmax
for(i=0i<pop_sizei++)
{
g=gene+i*g_length
j=gene_to_pheno(g,g_length)
x=X1+(int)(j*f)
y=Y1+YR1-*(func+j)*YR1
g_line(x,y-10,x,y,15)
}
/* 适应度曲线的更新 */
if(num!=1 &&num<=XR2/STEP)
{
if(num%10==0) /* 每隔10代更新一次 */
{
x=X2+(num-1)*STEP
g_line(x,Y2+1,x,Y2+YR2-1,1)
sprintf(c,"%d",num)
if(num<100 || num%20==0)
g_text(x-8,Y2+YR2,15,c)
}
x_old=X2+(num-1)*STEP
x=x_old+STEP
y_old=Y2+YR2-(int)(m_f_old*YR2)
y=Y2+YR2-(int)(max_fit*YR2)
g_line(x_old,y_old,x,y,11)
y_old=Y2+YR2-(int)(a_f_old*YR2)
y=Y2+YR2-(int)(avg_fit*YR2)
g_line(x_old,y_old,x,y,9)
}
}
void generation(gene,fitness,pop_size,g_length, c_rate,m_rate,new_gene,new_fitness,func,xmax)
/* 世代进化的模拟 */
unsigned char *gene /* 当前世代的个体遗传基因型 */
unsigned char *new_gene /* 新一代的个体遗传基因型 */
double *fitness /* 当前世代的个体适应度 */
double *new_fitness /* 新一代的个体适应度 */
double *func /* 优化函数 */
double c_rate,m_rate /* 交叉概率和变异概率 */
int pop_size, g_length/* 种群大小与染色体长度 */
{ int gen_max/* 最大模拟世代数 */
int i,j,k
double max_fit,avg_fit /* 当前代最大适应度和平均适应度 */
double m_f_old,a_f_old /* 新一代最大适应度和平均适应度 */
char choice[3]
setcolor(15)
disp_hz16("输入最大模拟世代数:",10,1,20)
gscanf(170,1,4,0,3,"%s",choice)
gen_max=atoi(choice)
m_f_old=0.0
a_f_old=0.0
for(i=0i<gen_maxi++)
{
if(i==gen_max-1)
{
printf("\n")
printf("************Gen.%d*************\n",i+1)
}
calc_fitness(gene,fitness,pop_size,g_length,func,
&max_fit,&avg_fit)
sga_reproduction(gene,fitness,new_gene,new_fitness,
pop_size,g_length)
for(j=0j<pop_sizej++)
{
*(fitness+j)=*(new_fitness+j)
for(k=0k<g_lengthk++)
*(gene+g_length*j+k)=*(new_gene+g_length*j+k)
}
sga_crossover(gene,pop_size,g_length,c_rate)
sga_mutation(gene,pop_size,g_length,m_rate)
g_plot_grph(i,gene,fitness,pop_size,g_length,func,
xmax,max_fit,m_f_old,avg_fit,a_f_old,gen_max)
m_f_old=max_fit
a_f_old=avg_fit
}
}
main() /* 主程序 */
{
/*当前代的个体遗传基因型与新一代的个体遗传基因型 */
unsigned char gene[POP_SIZE][G_LENGTH], new_gene[POP_SIZE][G_LENGTH]
/*当前代的个体适应度与新一代个体的适应度 */
double fitness[POP_SIZE], new_fitness[POP_SIZE]
/* 优化函数 */
double func[XMAX+1]
/* 初始化图形设置 */
g_init()
/* 生成优化函数 */
make_function(func,XMAX)
/* 初始化显示画面 */
g_init_grph(func,XMAX)
/* 初始化种群 */
initialize_gene(gene,POP_SIZE,G_LENGTH)
/* 世代进化模拟 */
generation(gene,fitness,POP_SIZE,G_LENGTH,
C_RATE,M_RATE,new_gene,new_fitness,func,XMAX)
setcolor(9)
disp_hz16("回车键结束",350,430,20)
getch()
}
哈,如果你不计较算法复杂度的话#include <iostream>
#include <cmath>
using namespace std
int main()
{
int a = INT_MIN
int b = INT_MIN
for(a <= INT_MAX++a)
{
b = INT_MIN
for(b <= INT_MAX++b)
{
if( (a+b==99)&&(3*a+4*b==306) )
{
cout <<"A=" <<a <<"B=" <<b <<endl
}
}
}
return 0
}
当然了，这需要解为整数才行
你可以缩小范围,比如0-100或0-1000
反正现在这样,估计要等个10分钟吧
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）