eclipse 网站开发源码,seo技术快速网站排名,最新网络舆情,wordpress精品插件基本计算器: 224. 基本计算器 - 力扣#xff08;LeetCode#xff09; 本体思路为#xff0c;将中缀表达式转为后缀表达式#xff0c;通过后缀表达式进行运算。 中缀表达式:
我们日常生活中熟知的表达式如12-30 就是一个中缀表达式。 后缀表达式: 150. 逆波兰表达式求值 - …基本计算器: 224. 基本计算器 - 力扣LeetCode 本体思路为将中缀表达式转为后缀表达式通过后缀表达式进行运算。 中缀表达式:
我们日常生活中熟知的表达式如12-30 就是一个中缀表达式。 后缀表达式: 150. 逆波兰表达式求值 - 力扣LeetCode 后缀表达式Postfix Expression也称为逆波兰表示法Reverse Polish Notation, RPN是一种数学表达式的表示方法。在这种表示法中运算符紧跟在操作数之后而不是像中缀表达式如 3 4那样将运算符放在操作数中间。
中缀表达式常规的数学表达式如 3 4 * 2。
后缀表达式运算符放在操作数之后如 3 4 2 * 。 后缀表达式运算:
后缀表达式运算思想为遇到操作数入栈遇到操作符则弹出栈顶的两个元素进行操作符匹配运算当表达式结束后留在栈顶的操作数就是最后的值。 这里将元素弹出时候需要进行左元素与右元素区分因为如果是*则左元素与右元素没区别但如果是-/谁在左谁在右区别就很大。 中缀转后缀:
中缀想要转成后缀需要把握两个思想
遇到操作数载入容器遇到操作数判断操作数的优先级进行入栈 如果栈里没有操作符则直接入栈如果栈顶操作符优先级比当前操作符优先级低则当前操作符入栈如果比当前栈顶操作符优先级低或相等,这表示前面的操作符可以进行运算弹出当前栈顶操作符载入容器。将当前操作符继续入栈。 如果遇到( )我们可以将它看作为一个子表达式进行递归运算。 以下是代码实现:
#includeiostream
#includemap
#includevector
#includestack
#includefunctional
#includealgorithm
#includestring
using namespace std;class Solution
{
public:void TrunSuffix(string s, size_t i, vectorstring ret){stackchar st;mapchar, int mp{ {,1},{-,1} ,{*,2} ,{/,2} };while (i s.size()){if (isdigit(s[i])){string num;for (; i s.size(); i){if (isdigit(s[i])){num s[i];}else{break;}}ret.push_back(num);}else if (s[i] (){TrunSuffix(s, i, ret);}else if (s[i] )){i;while (!st.empty()){char ch st.top();st.pop();ret.push_back(string(1, ch));}return;}else{if (st.empty() || mp[st.top()] mp[s[i]]){st.push(s[i]);}else{char ch st.top();st.pop();ret.push_back(string(1, ch));st.push(s[i]);}}}while (!st.empty()){char ch st.top();st.pop();ret.push_back(string(1, ch));}}int Suffix(vectorstring ret){mapstring, functionint(int, int)mp {{, [](int a, int b) {return a b; }},{ -, [](int a, int b) {return a - b; } },{ *, [](int a, int b) {return a * b; } },{/, [](int a, int b) {return a / b; }}};stackint st;for (auto e : ret){if (mp.count(e)){int right st.top();st.pop();int left st.top();st.pop();int r mp[e](left, right);st.push(r);}else{st.push(stoi(e));}}return st.top();}int calculate(string s){//12-(3*4)string news;for (size_t j 0; j s.size(); j){if (s[j] ! ){news s[j];}}s.swap(news);news ;for (size_t j 0; j s.size(); j){if (s[j] - (j 0 || (!isdigit(s[j - 1]) s[j - 1] ! )))){news 0-;}else{news s[j];}}s.swap(news);news ;int flag 0;for (int i 0; i s.size(); i){if (s[i] || s[i] - || s[i] * || s[i] /)flag 1;}if (!flag){string news;for (auto e : s){if (isdigit(e)){news e;}}return stoi(news);}vectorstring ret;size_t i 0;TrunSuffix(s, i, ret);return Suffix(ret);}
};int main()
{int n Solution().calculate( (1(452)-3)(68) );cout n endl;return 0;
} 说一下我在写这题的坑
这题力扣一开始会给出 “1 2 ( 4 - 5)”类似这种带空格的表达式所以在一开始的时候就需要先过滤一遍表达式将删除空格。 我们还需要确认是负数还是减号如果是负号妥妥的会坑。 所以我们还需要在” - ” 加以判断如果-前面是操作数则是正常-号。如果是操作符表示是一个负数所以我们在直接添加 ”-0” 添加成 0- 就更好的进行运算。 这里还有一个特殊案例 -号前面是 ) 而我们代码会识别成这是一个负数就会变成 所以还需要特殊判断如果是 ) 则不进行添加 “0-” 力扣给的测试用例里会有(1231231)类似这种。如果不特殊判断则会直接取到1及栈顶元素。所以我们在修正完字符串后进行检查如果没有操作符直接进行返回。 最后我们可能会在调试期间进行输出打印。所以在提交答案时候请将输出打印注释否则在最后几个测试用例里会有非常长的表达式会导致超出运行时间过不了。
