南邮简易计算器后缀转中缀

通达学院算法与数据结构设计报告（2014/2015学年第二学期）题目：专业学生姓名班级学号指导教师戴华指导单位计算机科学与技术系日期2015.4.13–2015.4.17题目：简易计算器基本要求：计算器是人们日常生活中常用的工具，本题目目标是实现一个支持混合运算（加、减、乘、除、乘方、括号）的计算器程序。(1)输入混合运算表达式，如(203+21-8/2)*32+3^3，输出正确的计算结果；(2)乘方包含平方、三次方、…、N次方；(3)当输入错误的表达式或计算结果溢出时，能给出正确的出错分析。提高要求：(1)设计友好窗口界面；(2)考虑采用性能好的算法。设计提示：利用后缀表达式计算方法实现计算器。参考资料：《数据结构—使用C＋＋语言描述》陈慧南东南大学出版社2000.《C程序设计》谭浩强清华大学出版社2001.《C++语言程序设计》郑莉董渊清华大学出版社2002.分配该题目的学生学号：13002103，13002109，13002116，13002122，13002129一、课题内容和要求1.表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。例如：a*(x+y)/(b-x)转换后得：axy+*bx-/2.（1（2）中缀表达式字符串char*infix;（3）后缀表达式字符串char*postfix;3.转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；左括号，进栈，直到遇见相配的右括号，才出栈；右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；对于运算符，分两种情况处理：该运算符的优先级大于栈顶符号的优先级，则入栈；若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。二、数据结构说明1.中缀转后缀部分voidpopAll(stackchar&stk,charpostfix[],intpostIndex){while(stk.size()!=0){postfix[postIndex++]=stk.top();stk.pop();}postfix[--postIndex]='\0';//在'#'处插入结束符}voidinfix2postfix(charinfix[],charpostfix[]){intinIndex=0,postIndex=0;stackcharoperators;operators.push(ENDCHAR);//压入ENDCHAR避免后面操作到空栈而出错while(infix[inIndex]){if(isdigit(infix[inIndex])||infix[inIndex]=='.')//数字直接输出到postfix中{postfix[postIndex++]=infix[inIndex];}elseif(infix[inIndex]=='('){//'('入栈operators.push(infix[inIndex]);}elseif(infix[inIndex]==')')//括号与运算符分开处理{/*当当前符号为')'则依次弹出栈中符号直至遇到'('*/while(operators.top()!='('){postfix[postIndex++]=operators.top();operators.pop();}operators.pop();//弹出'('}elseif(isOperator(infix[inIndex])){/*将当前操作符与栈顶操作符比较若小于等于栈顶操作符则将栈顶操作符弹出直至当前操作符大于栈顶操作符最后将当前操作符入栈*/postfix[postIndex++]='';//隔开操作数while(priority(infix[inIndex])=priority(operators.top())){postfix[postIndex++]=operators.top();operators.pop();}operators.push(infix[inIndex]);}++inIndex;}popAll(operators,postfix,postIndex);//全部操作符出栈}2.设置优先级别intpriority(charc){switch(c){caseENDCHAR:case'(':return0;case'+':case'-':return1;case'*':case'/':return2;case'^':return4;default:coutInvalidOperator!:'c'endl;exit(1);}}3.后缀表达式的计算表达式求值部分doublecalc(doublenum1,doublenum2,charop){switch(op){case'+':returnnum1+num2;case'-':returnnum1-num2;case'*':returnnum1*num2;case'/':returnnum1/num2;case'%':returnfmod(num1,num2);case'^':returnpow(num1,num2);default:exit(1);}}doublereadNumber(char**string){doubleintNumber=0;doublefloatNumber=0;inttimes=1;while(isdigit(**string)){intNumber=intNumber*10+**string-'0';++*string;}if(**string=='.'){++*string;while(isdigit(**string)){floatNumber=floatNumber+(**string-'0')*pow(0.1,times);++*string;}}returnintNumber+floatNumber;}doublecalcPostfix(charpostfix[]){doublenum1,num2;stackdoublenumbers;while(*postfix){if(isdigit(*postfix)){numbers.push(readNumber(&postfix));//读取数字}elseif(isOperator(*postfix)){/*取得2操作数执行当前运算并将结果入栈*/num2=numbers.top();numbers.pop();num1=numbers.top();numbers.pop();numbers.push(calc(num1,num2,*postfix++));}elseif(isspace(*postfix)){++postfix;//跳过空格}}returnnumbers.top();}三、算法设计流程图四、详细设计源代码：#includeiostream#includestack#includectype.h#includestdlib.h#includemath.h#defineENDCHAR'#'usingnamespacestd;//中缀转后缀部分intisOperator(charc){switch(c){case'+':case'-':case'*':case'/':case'^':return1;default:return0;}}intpriority(charc){switch(c){caseENDCHAR:case'(':return0;case'+':case'-':return1;case'*':case'/':return2;case'^':return4;default:coutInvalidOperator!:'c'endl;exit(1);}}voidpopAll(stackchar&stk,charpostfix[],intpostIndex){while(stk.size()!=0){postfix[postIndex++]=stk.top();stk.pop();}postfix[--postIndex]='\0';//在'#'处插入结束符}voidinfix2postfix(charinfix[],charpostfix[]){intinIndex=0,postIndex=0;stackcharoperators;operators.push(ENDCHAR);//压入ENDCHAR避免后面操作到空栈而出错while(infix[inIndex]){if(isdigit(infix[inIndex])||infix[inIndex]=='.')//数字直接输出到postfix中{postfix[postIndex++]=infix[inIndex];}elseif(infix[inIndex]=='('){//'('入栈operators.push(infix[inIndex]);}elseif(infix[inIndex]==')')//括号与运算符分开处理{/*当当前符号为')'则依次弹出栈中符号直至遇到'('*/while(operators.top()!='('){postfix[postIndex++]=operators.top();operators.pop();}operators.pop();//弹出'('}elseif(isOperator(infix[inIndex])){/*将当前操作符与栈顶操作符比较若小于等于栈顶操作符则将栈顶操作符弹出直至当前操作符大于栈顶操作符最后将当前操作符入栈*/postfix[postIndex++]='';//隔开操作数while(priority(infix[inIndex])=priority(operators.top())){postfix[postIndex++]=operators.top();operators.pop();}operators.push(infix[inIndex]);}++inIndex;}popAll(operators,postfix,postIndex);//全部操作符出栈}//表达式求值部分doublecalc(doublenum1,doublenum2,charop){switch(op){case'+':returnnum1+num2;case'-':returnnum1-num2;case'*':returnnum1*num2;case'/':returnnum1/num2;case'%':returnfmod(num1,num2);case'^':returnpow(num1,num2);default:exit(1);}}doublereadNumber(char**string){doubleintNumber=0;doublefloatNumber=0;inttimes=1;while(isdigit(**string)){intNumber=intNumber*10+**string-'0';++*string;}if(**string=='.'){++*string;while(isdigit(**string)){floatNumber=floatNumber+(**string-'0')*pow(0.1,times);++*string;}}returnintNumber+floatNumber;}doublecalcPostfix(charpostfix[]){doublenum1,num2;stackdoublenumbers;while(*postfix){if