题目描述
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。
输入格式
输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为0到231−1之间的整数。
输入数据保证这一行只有0~9、+、*这12种字符。
输出格式
输出只有一行，包含一个整数，表示这个表达式的值。
注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。
数据范围
0≤表达式中加法运算符和乘法运算符的总数≤105
输入样例：
1+1000003*1
输出样例：
4
样例
blablabla
算法1
(双栈模拟) $O(n)$
blablabla
时间复杂度
参考文献
这道题是要求去掉前导0的，刚开始没有考虑到其实不用管这一点（还是数据太水？），不过找到了一些字符串与数字和数字与字符串相互转化的函数，然后这种求表达式题目的题，在做了表达式求值4后其实就掌握了很多，我们可以给字符串加一个括号，然后每次将括号里面的全部算出（一个常用技巧）。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<ll>nums;
stack<char>ops;
const int M=10000;
void cal()
{
int a=nums.top();nums.pop();
int b=nums.top();nums.pop();
char c=ops.top();ops.pop();
int d;
if(c=='+')
{
d=b+a;
d%=M;
}
else if(c=='*')
{
d=b*a;
d%=M;
}
nums.push(d);
}
int main()
{
string str;
cin>>str;
str='('+str+')';
for(int i=0;i<str.size();i++)
{
if(str[i]>='0'&&str[i]<='9')
{
int j=i,t=0;
while(str[j]>='0'&&str[j]<='9')
{
t=t*10+str[j]-'0';
j++;
}
i=j-1;
nums.push(t%M);
}
else
{
char c=str[i];
if(c=='(')ops.push(c);
else if(c=='+')
{
while(ops.top()!='(')cal();
ops.push(c);
}
else if(c=='*')
{
while(ops.top()=='*')cal();
ops.push(c);
}
else if(c==')')
{
while(ops.top()!='(')cal();
ops.pop();
}
}
}
int t=nums.top();
cout<<t;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
1 利用stringstream
添加头文件 #include[HTML_REMOVED]
数字转字符串
#include [HTML_REMOVED]
#include [HTML_REMOVED]
int main(){
double a = 123.32;
string res;
stringstream ss; 定义流ss
ss << a; 将数字a转化成流ss
ss >> res; 将流ss转化成字符串
return 0;
}
字符串转数字
#include [HTML_REMOVED]
#include [HTML_REMOVED]
int main(){
double a ;
string res= “123.32”;
stringstream ss;
ss << res;
ss >> a;
return 0;
}
//此处包装了一个方法，将一位的数字转化成两位的字符串
//0->”00” 1->’‘01”
string transform(int num)
{
string res;
stringstream ss;
ss<[HTML_REMOVED]>res;
if(num<10)
{
res=”0”+res;
}
return res;
}
2.利用 sprintf()函数和sscanf()函数
sprintf() 用于将数字转化为字符串
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
int main()
{
char str[10];
int a=1234321;
//将整数转化为字符串
sprintf(str,”%d”,a);
int len=strlen(str);
cout<<”字符串”<<str<<endl;
cout<<”长度”<<len<<endl;
char str1[10];
double b=123.321;
/ /将浮点数转化为字符串
sprintf(str1,"%.3lf",b);
int len1=strlen(str1);
cout<<"字符串"<<str1<<endl;
cout<<"长度"<<len1<<endl;
return 0;
}
sscanf() 用于将字符串转化为数字
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
int main()
{
char str[]=”1234321”;
int a;
sscanf(str,”%d”,&a);
cout<<a<<endl;
char str1[]="123.321";
double b;
sscanf(str1,"%lf",&b);
cout<<b<<endl;
return 0;
}
C++ 代码
blablabla
