广州兼职网网站建设,云主机服务,网站建设程序员,十大外贸电商平台有哪些题目#xff1a;Basic Calculator 给定一个合法的运算表达式#xff0c;该表达式中只包含数字、、-、 、(、)。 思路#xff1a; 简单思考不用看成加减两种运算#xff0c;直接看成加法#xff0c;只不过由正负#xff1b; 如何处理括号呢#xff1f;因为只看成加法Basic Calculator 给定一个合法的运算表达式该表达式中只包含数字、、-、 、(、)。 思路 简单思考不用看成加减两种运算直接看成加法只不过由正负 如何处理括号呢因为只看成加法括号会影响的是数值的正负那么通过去括号运算法则来修改当前值的正负就可以了。 具体来说保存括号前的正负括号内的正负都要乘以保存的正负。 int LeetCode::calculate(string s){int result 0;vectorintsign(2, 1);//当前元素的正负,如果输入是7-?可能会两次pop_back为了不去判断是否为空for (size_t i 0; i s.size(); i){if (s[i] 0){//因为题目说只有数字、、-、*、/、(、)、 这几种字符其他都比数字小int k 0;while (i s.length() isdigit(s[i]))k k * 10 s[i] - 0;k k*sign.back();result k;sign.pop_back();--i;//i退回来}else if (s[i] )){sign.pop_back();}else if (s[i] ! ){//如果是左括号就将括号展开需要乘以括号外面的符号所以要乘以sign.back()sign.push_back(sign.back()*(s[i] - ? -1 : 1));}}return result;
} 题目Basic CalculatorII 给定一个合法的运算表达式该表达式中只包含数字、、-、 、/、*。 和上面相比增加了乘除去掉了括号。 思路 有了乘除就有不同的运算优先级这里通过每次将加减的结果加到最终结果里面使每次*/运算的时候cur会从零开始这样屏蔽了前面的运算结果过从而避免的优先级的判断 int LeetCode::calculate(string s){int result 0,cur 0;char op ;//默认当前运算符为加for (size_t i 0; i s.size(); i){if (isdigit(s[i])){//数字int k 0;while (i s.length() isdigit(s[i]))k k * 10 s[i] - 0;//计算数值switch (op){case :cur cur k;break;case -:cur cur - k;break;case *:cur cur * k;break;case /:cur cur / k;break;default:return -1;//表达式有误}--i;}else if(s[i] ! ){if (s[i] || s[i] -){//加减运算符与顺序无关由于没有括号每次加减的值立即给resultresult cur;cur 0;}op s[i];//遇到乘除的时候cur总是从零开始的所以前面的运算没有影响}}return result cur;
} 思路 其实考虑第一题的思路可以将加减法去掉从而避免判断运算优先级因为乘除的优先级是一样的加减变成数字的符号这样每次就只用计算乘除 int calculate(string s) {stackint myStack;char sign ;//保存运算符int res 0, tmp 0;for (unsigned int i 0; i s.size(); i) {if (isdigit(s[i]))tmp 10*tmp s[i]-0;//计算出数值if (!isdigit(s[i]) !isspace(s[i]) || i s.size()-1) {if (sign -)myStack.push(-tmp);//减法变成负数else if (sign )myStack.push(tmp);//加法变成正数else {int num;//乘除运算if (sign * )num myStack.top()*tmp;elsenum myStack.top()/tmp;myStack.pop();//将参与的上一个数值出栈myStack.push(num);//运算结果入栈} sign s[i];tmp 0;}}while (!myStack.empty()) {//所有的结果加起来res myStack.top();myStack.pop();}return res;
} 以上的方法都是根据题意而取巧如果放开运算表达式的限制算法就不能用了。 思路 这里有正常的通过双栈存储数值和运算符遇到左括号运算符或数值都入栈遇到运算符就先判断优先级将要入栈的运算符优先级低于或等于栈顶的运算符就将栈顶的运算符出栈并计算数值知道栈顶的运算符优先级较低 优先级顺序从高到低如下 * / - (;加减的优先级是一样的但是栈顶的运算符优先级高于正在访问的运算符优先级即正在访问的/- 栈顶的/-。 这样就可以按照通常的运算习惯让程序计算表达式的结果。 int LeetCode::calcu(stackint num, stackchar sign){//运算符栈和数值栈出栈做运算if (num.empty())return -1;//表达式有误int k num.top();num.pop();//都是双目运算符还需要一个数if (num.empty())return -1;//表达式有误int m num.top();num.pop();char ch sign.top();sign.pop();int result 0;switch (ch){case :result m k;break;case -:result m - k;break;case *:result m * k;break;case /:result m / k;break;default:return -1;//表达式有误}return result;
}int LeetCode::operatorPriority(char op1, char op2){//判断优先级if (op1 ( || op2 ()return false;if (op1 || op1 -){if (op2 * || op2 /)return false;}return true;
}int LeetCode::calculate(string s){stackintnum;//数字栈stackcharop;//符号栈int i 0;while (i s.length()){if (isdigit(s[i])){//是数字//拼接数字int k 0;while (i s.length() isdigit(s[i]))k k*10 s[i] - 0;num.push(k);continue;}else if (s[i] )){//是右括号if (op.empty())return -1;if (op.top() (){op.pop();}else{//符号栈出栈并计算知道遇到左括号或某个栈为空while (!op.empty() op.top() ! (){num.push(calcu(num, op));}op.pop();}i;}else if (!isspace(s[i])){//非空格符这里认为是运算符或左括号//下一个运算符入栈前先计算栈顶的运算符while (!op.empty() operatorPriority(op.top(),s[i]))num.push(calcu(num, op));op.push(s[i]);}i;}while (!op.empty()){num.push(calcu(num,op));}return num.top();
} 转载于:https://www.cnblogs.com/yeqluofwupheng/p/6810233.html
