题意:
计算数学表达式的值,
数学表达式的定义: 4个[0-9]表示数字的字符 ,3个[+-x/]表示运算的字符
可以用正则为: ([0-9][+-x/]){3}[0-9]
例如: 5+2/1x3
2-1+7x3
3x3/3x3
找到图片了,不啰嗦了...
这道题只有7个字符,数字只有一位不算太难
先算乘除,后算加减,考试的时候就是这样做的,用stack完美解决
但如果加大难度....
1) 数字允许有多位比如 1314-521*233
2) 再比如如果有括号呢 -1-(1-(-9))
让我们按照函数化的思想逐渐完善我们的代码
(1) 7个字符版本
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int get_ans (string str) {
stack <int> s;
int flag=;
for (int i=;i<str.size();i++) {
if (str[i]>=''&&str[i]<='') s.push( flag*(str[i]-''));
else if (str[i]=='-' || str[i]=='+') {
if (str[i]=='-') flag=-;
else flag=;
}
else {
int x1=s.top(); s.pop();
i++; // importment !!
int x2=str[i]-'';
if (str[i-]=='/') s.push(x1/x2);
else s.push(x1*x2);
}
}
int sum=;
while (!s.empty()) {
sum+=s.top();
s.pop();
}
return sum;
}
int main ()
{
int T; cin>>T;
while (T--) {
string str; cin>>str;
cout<<get_ans(str)<<endl;
}
return ;
}
2 允许有连续的输入数字: 233*521
我们加入一个输入接口get_num: 如果下一个字符是数字,就一直读下去
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std; int get_num(string str,int &k) {
// 从k开始一直读所有的数字字符
int ans=;
for (;k<str.size();k++) {
if (str[k]>='' && str[k]<='')
ans=ans*+str[k]-'';
else break;
}
k--; // i 此时指向最后一个数字的位置
return ans;
} int get_ans (string str) {
stack <int> s;
int flag=;
for (int i=;i<str.size();i++) {
if (str[i]>=''&&str[i]<='') {
int num=get_num(str,i);
s.push(flag*num);
}
else if (str[i]=='-' || str[i]=='+') {
if (str[i]=='-') flag=-;
else flag=;
}
else {
char ch=str[i];
int x1=s.top(); s.pop();
i++;
int x2=get_num(str,i);
if (ch=='/') s.push(x1/x2);
else s.push(x1*x2);
}
}
int sum=;
while (!s.empty()) {
sum+=s.top();
s.pop();
}
return sum;
} int main ()
{
int T; cin>>T;
while (T--) {
string str; cin>>str;
cout<<get_ans(str)<<endl;
}
return ;
}
3 最难的部分,遇到括号怎么办---
我们也只需要加一个接口
其核心就是把一对括号里面的字符,放入我们之前的接口算出结果,从而达到去除括号的效果
例子: 1*(3-(5-4)) ->1*(3-1)->1*2>2
总之就是把一个问题切分成一个一个小问题
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
string to_str (int x) {
if (x==) return "";
string ans;
bool flag=;
if (x<) {
flag=;
x=-x;
}
while (x) {
ans+=x%+'';
x/=;
}
if (flag) ans+='-';
return ans;
} int get_num(string str,int &k) {
int ans=;
for (;k<str.size();k++) {
if (str[k]>='' && str[k]<='')
ans=ans*+str[k]-'';
else break;
}
k--; // i 此时指向最后一个数字的位置
return ans;
} int get_no_ans (string str) {
stack <int> s;
int flag=;
for (int i=;i<str.size();i++) {
if (str[i]>=''&&str[i]<='') {
int num=get_num(str,i);
s.push(flag*num);
}
else if (str[i]=='-' || str[i]=='+') {
if (str[i]=='-') {
if (i-&&str[i-]=='-') flag=-flag;
else flag=-;
}
else flag=;
}
else {
char ch=str[i];
int x1=s.top(); s.pop();
i++;
int x2=get_num(str,i);
if (ch=='/') s.push(x1/x2);
else s.push(x1*x2);
}
}
int sum=;
while (!s.empty()) {
sum+=s.top();
s.pop();
}
return sum;
} int get_ans (string str) {
str="("+str+")";
stack <char> s;
int ans;
for (int i=;i<str.size();i++) {
if (str[i]==')') {
string tmp;
while (s.top()!='(') {
tmp+=s.top();
s.pop();
}
s.pop();
reverse(tmp.begin(), tmp.end());
int num=get_no_ans(tmp);
//cout<<tmp<<"@@@"<<num<<endl;
tmp=to_str(num);
for (int j=tmp.size()-;j>=;j--) s.push(tmp[j]);
if (i==str.size()-) ans=num;
}
else s.push(str[i]);
}
return ans;
} int main ()
{
int T; cin>>T;
while (T--) {
string str; cin>>str;
cout<<get_ans(str)<<endl;
}
return ;
}