首页 > 代码库 > 华为机试—四则运算

华为机试—四则运算

题目:四则运算

问题描述:
输入一个只包含个位数字的简单四则运算表达式字符串,计算该表达式的值
注:
3.1、表达式只含 +, -, *, / 四则运算符,不含括号
3.2、表达式数值只包含个位整数(0-9),且不会出现0作为除数的情况
3.3、要考虑加减乘除按通常四则运算规定的计算优先级
3.4、除法用整数除法,即仅保留除法运算结果的整数部分。比如8/3=2。输入表达式保证无0作为除数情况发生
3.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<cstdio>
#include<stack>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
stack<char>op;
stack<int>nums;
int main(int argc, char *argv[])
{
    string s;

    while(getline(cin,s)!=NULL)
    {
        while(!op.empty())op.pop();
        while(!nums.empty())nums.pop();
        int len=s.size();
        int i=0;
        while(s[i]!='"')i++;
        for(i++;i<len-1;++i)
        {
            if(s[i]=='+'||s[i]=='-')op.push(s[i]);
            else if(s[i]=='*'||s[i]=='/')
            {
                char t=s[i];
                i++;
                int a=nums.top();
                nums.pop();
                int b=s[i]-'0';
                int c;
                if(t=='*')
                    c=a*b;
                if(t=='/')
                    c=a/b;
                nums.push(c);
            }
            else
                nums.push(s[i]-'0');
        }
        while(!op.empty())
        {
            char o=op.top();
            op.pop();
            int a=nums.top();
            nums.pop();
            int b=nums.top();
            nums.pop();
            int c;
            if(o=='+')
                c=a+b;
            if(o=='-')
                c=b-a;
            nums.push(c);
        }
        printf("%d\n",nums.top());
    }
    return 0;
}

测试数据:

char *expStr = "1+4*5-8/3"
char *expStr = "8/3*3"
char *expStr = "2*3+3-2"
char *expStr = "3-9/2"

结果:

技术分享

华为机试—四则运算