题目描述:
给定一个字符串描述的算术表达式,计算出结果值。
输入字符串长度不超过100,合法的字符包括”+, -, *, /, (, )”,”0-9”,字符串内容的合法性及表达式语法的合法性由做题者检查。本题目只涉及整型计算。
输入描述:
输入算术表达式
输出描述:
计算出结果值
示例:
输入:
400+5
输出:
405
解题思路:
本题有两个要点:
1.检查表达式合法性。首先利用sheet字典,确保字符串中字符都符合要求;其次判断左右括号数是否一致。
2.calculate函数实现表达式计算。左右有括号就缩进;先找加减法再找乘除;找到运算符后,左右两侧字符串再调用calculate,进行递归;递归至不再包含运算符后退回,返回数字。递归结束,结果输出。
测试代码:
#include <iostream> #include <string> #include <vector> using namespace std; vector<char> sheet={'+','-','*','/','(',')','0','1','2','3','4','5','6','7','8','9'}; // 检查合理性 bool check(string &s) { int left=0; int right=0; for(int i=0;i<s.size();++i) { bool isok=false; for(int j=0;j<sheet.size();++j) { if(s[i]=='(') left++; if(s[i]==')') right++; if(s[i]==sheet[j]) isok=true; } if(!isok) return false; } if(left!=right) return false; return true; } // 算术表达式计算 int calculate(string &s,int start,int end) { if(s[start]=='('&&s[end-1]==')') { ++start; --end; } int layer=0,am=0,md=0; bool flag=false; for(int i=start;i<end;++i) { if(s[i]=='(') { ++layer; flag=true; } else if(s[i]==')') { --layer; flag=true; } else if((s[i]=='+'||s[i]=='-')&&!layer) am=i; else if((s[i]=='*'||s[i]=='/')&&!layer) md=i; } if (am > start) { if (s[am] == '+') return calculate(s, start, am) + calculate(s, am+1, end); else return calculate(s, start, am) - calculate(s, am+1, end); } else if (md > start) { if (s[md] == '*') return calculate(s, start, md) * calculate(s, md+1, end); else return calculate(s, start, md) / calculate(s, md+1, end); } else if(flag) return calculate(s,start+1,end-1); else return stoi(s.substr(start,end-start)); } int main() { string str; while(cin>>str) { if(!check(str)) cout<<-1<<endl; else cout<<calculate(str, 0, str.size())<<endl; } return 0; }