动态规划求表达式最大值

《动态规划求表达式最大值》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//随便输入一个不带括号的表达式，该程序可以自动对该表达式添加合适的括号，以使表达//式的值达到最大。#includeintnumbers[10];charoperators[10];intCalculate(inta,intb,charoperators){if(operators=='+'){returna+b;}elseif(operators=='-'){returna-b;}elseif(operators=='*'){returna*b;}return-100000

2、;}voidTraceBack(inti,intj,intseparate[][10]){if(i==j){printf("%d",numbers[i]);}else{printf("(");TraceBack(i,separate[i][j],separate);printf("%c",operators[separate[i][j]]);TraceBack(separate[i][j]+1,j,separate);printf(")");}}intmain(){charexpression[

3、100];printf("请输入一个算术表达式：");scanf("%s",expression);inti=0,j=0,k=0,n=0,sum=0;while(expression[i]!=''){while(expression[i]>='0'&&expression[i]<='9'){sum=sum*10+(expression[i]-'0');i++;}numbers[j]=sum;j++;sum=0;if(expression[i]==''){break;}operator

4、s[k]=expression[i];k++;i++;}numbers[j]='';//j代表数组numbers的长度operators[k]='';//k代表数组operators的长度intmaximum[10][10];intseparate[10][10];for(i=0;i

5、[j]=Calculate(maximum[i][i],maximum[i+1][j],operators[i]);separate[i][j]=i;for(intk=i+1;kmaximum[i][j]){maximum[i][j]=t;separate[i][j]=k;}}}}printf("加括号后的表达式为：");TraceBack(0,n-

6、1,separate);printf("");printf("结果为：%d",maximum[0][n-1]);return0;}运行结果如下：