1、问题描述
对于给定的一个表达式，表达式中可以包括常数、算术运行符（包括：“+”、 “-”、“*”、“/”、“%”（求余运算）、“^”（乘幂运算）、“！”（阶乘运算））和括 号，编写一个简单计算器，实现表达式的计算。
基本要求：从键盘输入一个正确的表达式，将表达式转换为对应的后缀表达式，并计算后缀 表达式的值。对于表达式中的简单错误（如，除数不能为零、负数无法求阶乘等），能够给出提 示，并给出错误信息；表达式中可以包括单个字母表示的变量。
提高要求：完成基本要求的基础上，能够支持一部分不规范的表达式（如，3-3+-6），支持 科学计数法表示的数（如，19971400000000 表示为：1.99714E13），并具有图形用户界面的简单计算器
2．需求分析
软件的基本功能：由键盘输入中缀表达式，程序可以将输入的中缀表达式转换成对应的后缀表达式，并计算后缀表达式的值。对于在输入时发生的简单错误，程序可以给出提示。本程序支持含负数、小数、多位数等多种操作数的处理，可以计算含加、减、乘、除、求余、求幂等多种运算符的表达式，并能判断表达式括号是否匹配。
输入/输出形式：用户可以通过控制台，根据输入提示。
输入形式：
①正确的不含字母变量的中缀表达式；
②含有简单错误的中缀表达式。
输出形式：
①对于正确的中缀表达式，可以输出其转化后的后缀表达式及表达式的计算结果；
②对于含有简单错误的中缀表达式，程序将自动输出错误提示，并给出错误信息。
测试数据要求：用户可以输入一个符合要求的中缀表达式，也可以输入一个包含简单错误的表达式。表达式中可以包括各种类型的常数以及负数等，操作符包括（+、-、*、/、%、^）等，同时表达式还可以包括各种括号。
3．所要利用的数据结构：栈
操作方法：
- 为将中缀表达式转换为后缀表达式并进行计算 ，函数首先会调 用Fun函数已检测表达式括号是否匹配，若不匹配则返回主函数。从左至右扫描 中缀表达式，遇到运算符时，比较其与s1栈顶运算符的优先级遇到操作数时， 将其压入s2遇到括号时如果是左括号’(’，则直接压入s1如果是右括号’)’， 则依次弹出s1栈顶的运算符，并压入s2中，直到遇到左括号’('为止，将这个 左括号从s1中弹出丢弃（这时候消除了一对括号）将s1中剩余的运算符依次弹 出并压入s2中依次弹出s2中的元素并输出，并将输出结果逆序，即得到后缀表 达式。从左至右扫描，若为数字，依次压入栈遇到运算符，依次弹出s1，s2， 计算s2（+，-，*，/）s1的结果并压入栈。
伪代码：
ADT SeqStack
Data
栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系
Operation
SeqStack
前置条件：栈不存在
输入：无
功能：栈的初始化
输出：无
后置条件：构造一个空栈
~ SeqStack
前置条件：栈已存在
输入：无
功能：销毁栈
输出：无
后置条件：释放栈所占用的存储空间
Push
前置条件：栈已存在
输入：元素值x
功能：在栈顶插入一个元素x
输出：如果插入不成功，抛出异常
后置条件：如果插入成功，栈顶增加了一个元素
Pop
前置条件：栈已存在
输入：无
功能：删除栈顶元素
输出：如果删除成功，返回被删元素值，否则，抛出异常
后置条件：如果删除成功，栈顶减少了一个元素
GetTop
前置条件：栈已存在
输入：无
功能：读取当前的栈顶元素
输出：若栈不空，返回当前的栈顶元素值
后置条件：栈不变
Empty
前置条件：栈已存在
输入：无
功能：判断栈是否为空
输出：如果栈为空，返回1；否则，返回0
后置条件：栈不变
End ADT
代码功能实现：
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include <math.h>
#define pi 3.1415926
using namespace std;
/***************************************************************************************************************************************/
/***函数定义部分***/
void adorn(char adorn,int n);//装饰函数
int fun(char *c1, int s, int e);//判断括号是否匹配
void PrintList(int top,float a[]);//打印计算结果
char input();//从键盘中读取数据
char Change(char c1[]); //将中缀表达式转换为后缀表达式并进行计算
int main();//使系统可以在函数内调用main函数
/***************************************************************************************************************************************/
/***************************************************************************************************************************************/
/***定义三个字符串，以便实现栈操作 ***/
char c1[1024];//用于存储输入的中缀表达式
char c2[1024];//为栈用于转化过程中对数和操作符进行压栈
char c3[1024];//用于元素出栈后进行相关运算，并将最终结果进行重新压栈
/***************************************************************************************************************************************/
/***************************************************************************************************************************************/
/***定义全局变量***/
float a[1024];// 用于最后计算结果的输出使用
int count=0;
/***************************************************************************************************************************************/
/***************************************************************************************************************************************/
/***各子函数实现部分***/
void adorn(char adorn,int n)//装饰函数
{
for(int i=0;i<n;i++)
{
putchar(adorn);//通过ASCLL码判断如果是数字则将ASCLL码-48转换为字符
}
putchar('\n'); //强制在字符串的结尾加上\n,方便计算字符串内的个数
}
int fun(char *c1, int s, int e)//判断括号是否匹配 （1匹配；0不匹配）
{
char L;
char R;
while((s<=e))
{
switch(c1[s])
{
case '(': L = c1[s];
R = ')';
break;
case '[': L = c1[s];
R = ']';
break;
case '{': L = c1[s];
R = '}';
break;
case ')': return 0;
case ']': return 0;
case '}': return 0;//若输入字符串为以上字符，则返回0
default:
L = '\0';
break;
}
if(c1[s] == L)
{
int p = 1;
int q=0;
int x = s+1;//t为s的下一个字符
while((x<=e)) // 搜索匹配的右括号
{
if(c1[x] == L)
p++;
if(c1[x] == R)
q++;
if(q>p)
return 0;
if(p == q) // 再对已匹配括号里面的括号进行匹配
{
if(fun(c1, s+1, x-1) == 0) // 递归调用，从最外层的括号分别向内匹配
return 0;
s=x;
break;
}
x++;
}
if(p>q)
return 0;
}
s++;
}
return 1;//都匹配上返回1
}
void PrintList(int top,float a[])//打印计算结果
{
cout<<"计算结果为:"<<endl;
if(a[top]>1000||a[top]<0.001) //科学计数法
printf("%.3E\n",a[top]);
else if(a[top]<=1000||a[top]>=0.001)
printf("%.8f\n",a[top]);
adorn('-',90);
}
char input()//从键盘中读取数据
{
int count=0;
int i;
int j;
int m;
int n;
int top=0;
int v=-1;
int u=0;
fflush(stdin);
gets(c1);//输入c1
}
char Change(char c1[])//将中缀表达式转换为后缀表达式并进行计算
{
fflush(stdin);
int count=0;
int i;
int j;
int m;
int n;
int top=0;
int v=-1;
int u=0;
int k=strlen(c1);
int r= fun(c1, 0, k-1);
if(r != 1)
{
printf("**括号不匹配，请重新输入**：\n");
loop:
input();
if(*c1=='#')
{
main();//返回主函数
}
else
{
Change(c1);
}
}
else
{
for(i=0;i<k;i++)//对输入的数组进行后缀表达式转换
{
switch(c1[i])
{
case '(':
c2[++top]=c1[i];
break;
case '+':
case '-':
while(top>0 && c2[top]!='(')//判断栈顶的元素是否为括号，且栈不空时 ，将栈中的前两个元素进行出栈与运算，将运算的结果进行重新入栈
{
c3[++v]=c2[top];
c3[++v]=' ';
top--;
}
c2[++top]=c1[i]; //当栈空或者遇到(时，将"-"直接入栈
break;
case '*':
case '/':
while(top>0 && c2[top]!='(' && c2[top]!='+' && c2[top]!='-')//考虑优先级
{
c3[++v]=c2[top];
c3[++v]=' ';
top--;
}
c2[++top]=c1[i];
break;
case '%':
while(top>0 && c2[top]!='(' && c2[top]!='+' && c2[top]!='-')//考虑优先级
{
c3[++v]=c2[top];
c3[++v]=' ';
top--;
}
c2[++top]=c1[i];
break;
case '^':
while(top>0 && c2[top]!='(' && c2[top]!='+' && c2[top]!='-')//考虑优先级
{
c3[++v]=c2[top];
c3[++v]=' ';
top--;
}
c2[++top]=c1[i];
break;
case '!':
while(top>0 && c2[top]!='(' && c2[top]!='+' && c2[top]!='-')//考虑优先级
{
c3[++v]=c2[top];
c3[++v]=' ';
top--;
}
c2[++top]=c1[i];
break;
case ')':
while(c2[top]!='('){
c3[++v]=c2[top];
c3[++v]=' ';
top--;
}
top--;
break;
default:
c3[++v]=c1[i];
if(c1[i+1]>'9' || c1[i+1]<'0')
c3[++v]=' ';
break;
}
}
while(top>0 && c2[top]!='(')
{
c3[++v]=c2[top];
c3[++v]=' ';
top--;
}
cout<<"其后缀表达式为："<<endl;
puts(c3);
top=0;
float sum;
k=strlen(c3);
for(i=0;i<k;i++)
{
if(c3[i]==' ')
{
;
}
else if(c3[i]=='+')
{
sum=a[top-1]+a[top];
a[--top]=sum;
}
else if(c3[i]=='-')
{
sum=a[top-1]-a[top];
a[--top]=sum;
}
else if(c3[i]=='*')
{
sum=a[top-1]*a[top];
a[--top]=sum;
}
else if(c3[i]=='/')
{
if(a[top]==0)
{
cout<<"**输入错误，被除数不能为0，请重新输入**："<<endl;
goto loop;
}
else
{
sum=a[top-1]/a[top];
a[--top]=sum;
}
}
else if(c3[i]=='%')
{
if(a[top]==0)
{
cout<<"**输入错误，被取余数不能为0，请重新输入**："<<endl;
goto loop;
}
else
{
int sum1=a[top-1]*10;
int sum2=a[top]*10;
sum=(sum1%sum2)/10;
a[--top]=sum;
}
}
else if(c3[i]=='^')
{
sum=pow(a[top-1],a[top]);
a[--top]=sum;
}
else if(c3[i]=='!')
{
if(a[top]<0)
{
cout<<"**输入错误，负数没有阶乘，请重新输入**："<<endl;//提示信息，并重新输入
input();
goto loop;
}
else
{
float sum=1;
for(int j=1;j<=a[top];j++)
{
sum=sum*j;
}
a[top]=sum;
}
}
else
{
int m=0;
while(c3[i]>='0' && c3[i]<='9')
{
m=10*m+c3[i]-'0';
i++;
}
a[++top]=m;
}
}
PrintList(top,a);
}
}
/***************************************************************************************************************************************/
/***************************************************************************************************************************************/
/***主函数部分***/
int main()
{
system("cls");//实现启动器的DOS功能，清除显示器屏幕上的内容，使DOS提示符到屏幕左上角
while(1)
{
fflush(stdin);//清除缓冲区的值
int count=0;
int i;
int j;
int m;
int n;
int top=0;
int v=-1;
int u=0;
adorn('-',90);
cout<<"**请输入需要计算的中缀表达式,直接回车即可，注意本系统只识别英文符号**：" <<endl;
cout<<"如果想退出本界面，请输入‘#’号键"<<endl;
input();
if(*c1=='#')
{
break;
}
else
{
Change(c1);
}
}
}
/***************************************************************************************************************************************/