[C++讨论站]如何将中值表达式转换为后缀表达式并计算

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);
		}	
	}
}
/***************************************************************************************************************************************/

上一篇:在excel中使用公式拼接字符串


下一篇:C语言复习总结