字符串四则运算表达式的计算（华为机试）

迷南。 2022-02-23 11:12 286阅读 0赞

最近做了一道华为的机试题。感觉自己的方法比网上的简洁。

3. 简单四则运算  
问题描述：  
输入一个只包含个位数字的简单四则运算表达式字符串，计算该表达式的值  
注  
1、表达式只含 +, -, \*, / 四则运算符，不含括号  
2、表达式数值只包含个位整数(0-9)，且不会出现0作为除数的情况  
3、要考虑加减乘除按通常四则运算规定的计算优先级  
4、除法用整数除法，即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生  
5、输入字符串一定是符合题意合法的表达式，其中只包括数字字符和四则运算符字符，除此之外不含其它任何字符，不会出现计算溢出情况

要求实现函数：  
int calculate(int len,char \*expStr)

【输入】  int len: 字符串长度；  
char \*expStr: 表达式字符串；  
【输出】  无  
【返回】  计算结果

示例  
1）  输入：char \*expStr = “1+4\*5-8/3”  
函数返回：19  
2）  输入：char \*expStr = “8/3\*3”  
函数返回：6\*/

#include <stdio.h>
    #include <memory>
    #include <string.h>
    /*****************************************/
    //这个算法开辟了额外的空间。
    //分析这个问题可以知道，字符串长度len是奇数（0不考虑）
    //数字的个数是len/2+1,符号的个数为len/2，然后将符号和数字存储起来
    //第一步处理所有的乘除法，此时有一个特点就是如果几个数
    //连续进行乘除法的时候就需要向前存储结果（为了方便后面的加减法运算）
    //算法复杂度O(n)
    /*****************************************/
    int calculate(int len,char *expStr)
    {	
    	int i,j,k,answer;
    	int* num=(int*)malloc((len/2+1)*sizeof(int));
    	char* exp=(char*)malloc(len/2);
    	for (i=0,j=0,k=0;i<len;i++)          //将符号和数字分开存储
    	{
    		if(i%2==0)
    			num[j++]=expStr[i]-'0';
    		else
    			exp[k++]=expStr[i];
    	}
    	//乘除法处理
    	for (i=0,j=1;i<len/2;i++)
    	{
    		if (exp[i]!='*'&&exp[i]!='/')
    		{
    			j=1;
    			continue;
    		}
    		if (exp[i]=='*')
    		{
    			num[i+1]*=num[i];
    			for (k=0;k<j;k++)
    			{
    				num[i-k]=num[i+1];
    			}
    			j++;
    		}
    		else if (exp[i]=='/')
    		{
    			num[i+1]=num[i]/num[i+1];
    			for (k=0;k<j;k++)
    			{
    				num[i-k]=num[i+1];
    			}
    			j++;
    		}
    	}
    	//处理加减法
    	answer=num[0];
    	for (i=0,j=1;i<len/2;i++)
    	{
    		if (exp[i]=='+')
    			answer+=num[i+1];
    		else if (exp[i]=='-')
    			answer-=num[i+1];
    	}
    	return answer;
    }
    
    int main()
    {
    	char* a="1+4*5-8/3*2*2*2";
    	int result=calculate(strlen(a),a);
    	//int result=calculate2(strlen(a),a);
    	printf("%d",result);
    	return 0;
    }
    
    //网上的答案，用栈进行操作
    int calculate2(int len,char *expStr)  
    {  
        struct  {  
            char opdata[200];  
            int top;  
        }opstack;  
        //定义操作符栈   
      
        opstack.top = -1;  
      
        int i=0;//遍历字符串的下标   
        int t=0;//当前后缀表达式的长度   
      
        char ch = expStr[i];  
      
        while (ch!='\0')  
        {  
            switch (ch)  
            {  
                case '+':  
                case '-':  
    			   while (opstack.top != -1)  
    			   {  
                        expStr[t] = opstack.opdata[opstack.top];  
                        opstack.top--;  
                        t++;  
                    }  
                    opstack.top++;  
                   opstack.opdata[opstack.top] = ch;  
                    break;  
                case '/':  
                    while (opstack.top != -1 && (opstack.opdata[opstack.top] =='*' || opstack.opdata[opstack.top] =='/') )  
                    {  
                        expStr[t] = opstack.opdata[opstack.top];  
                        opstack.top--;  
                        t++;  
                    }  
                    opstack.top++;  
                    opstack.opdata[opstack.top] = ch;  
                    break;  
                default:  
                    expStr[t] = ch;  
                    t++;  
                    break;  
            }  
            i++;  
            ch = expStr[i];  
        }  
      
        while (opstack.top != -1)//将栈中所有的剩余的运算符出栈   
        {  
            expStr[t] = opstack.opdata[opstack.top];  
            opstack.top--;  
            t++;  
        }  
      
        expStr[t]='\0';  
      
      
        struct  {  
            int numeric[200];  
            int top;  
        }data;  
      
        data.top = -1;  
      
        i=0;  
        ch = expStr[i];  
      
      
        while (ch!='\0')  
        {  
            if (ch>='0' && ch <= '9' )  
            {  
                data.top++;  
                data.numeric[data.top] = ch-'0';  
            }   
            else if('+' == ch)  
            {  
                int tmp = data.numeric[data.top-1]  + data.numeric[data.top];  
                data.top--;  
                data.numeric[data.top] = tmp;  
            }  
            else if('-' == ch)  
            {  
                int tmp = data.numeric[data.top-1]  - data.numeric[data.top];  
                data.top--;  
                data.numeric[data.top] = tmp;  
            }  
            else if('*' == ch)  
            {  
                int tmp = data.numeric[data.top-1]  * data.numeric[data.top];  
                data.top--;  
                data.numeric[data.top] = tmp;  
            }  
            else if('/' == ch)  
           {  
                if(data.numeric[data.top] == 0)  
                {  
                    printf("cannot be zero of the divide\n");  
                    exit(1);  
                }  
                int tmp = data.numeric[data.top-1] / data.numeric[data.top];  
                data.top--;  
                data.numeric[data.top] = tmp;  
            }  
            i++;  
            ch = expStr[i];  
        }  
      
        return data.numeric[data.top];  
    }