2.计算器实现
一.计算器实现思路
二.分析
这里我们要将后缀表达式,转换成为中缀表达式
建立一个栈存储运算数，读取后缀表达式，遇到运算数入栈，遇到运算符，出栈顶两个数进行运算，运算后将结果作为一个运算数入栈继续参与下一次的运算。读取表达式结束后，最后栈顶的数值就是运算结果。
三.中缀表达式转后缀表达式
四.代码实现
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<set> #include<map> #include<string> #include<vector> #include<stack> using namespace std; class Solution { public: map<char,int> op = { {'+',1}, {'-',1}, {'*',2}, {'/',2} }; //中缀转后缀 void toRPN(const string& s,size_t& i,vector<string>& v) { stack<char> st; while(i < s.size()) { if(isdigit(s[i])) { //操作数直接输出 string num; while(i < s.size() && isdigit(s[i])) { num += s[i++]; } v.push_back(num); } else if(s[i] == '(') { i++; toRPN(s,i,v); } else if(s[i] == ')') { while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } i++; return; } else { if(st.empty() || op[s[i]] > op[st.top()]) { st.push(s[i]); ++i; } else { char ch = st.top(); st.pop(); v.push_back(string(1,ch)); } } } while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } } }; int main() { size_t i = 0; vector<string> v; //string str = "1+2-3"; string str = "1+2-(3*4+5)-7"; Solution().toRPN(str, i, v); for (auto& e : v) { cout << e << " "; } cout << endl; return 0; }五.题目
题目链接:224. 基本计算器 - 力扣（LeetCode）
题目链接:
1.先将逆波兰表达式求值这个代码写出来
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; int i = 0; map<string,function<int(int,int)>> opFuncMap = { {"+",[](int x,int y){return x + y;}}, {"-",[](int x,int y){return x - y;}}, {"*",[](int x,int y){return x * y;}}, {"/",[](int x,int y){return x / y;}} }; for (auto& str : tokens) { if (opFuncMap.count(str)) { int right = st.top(); st.pop(); int left = st.top(); st.pop(); int ret = opFuncMap[str](left,right); st.push(ret); } else{ st.push(stoi(str)); } } return st.top(); } };2.代码结合
class Solution { public: map<char,int> op = { {'+',1}, {'-',1}, {'*',2}, {'/',2} }; //中缀转后缀 void toRPN(const string& s,size_t& i,vector<string>& v) { stack<char> st; while(i < s.size()) { if(isdigit(s[i])) { //操作数直接输出 string num; while(i < s.size() && isdigit(s[i])) { num += s[i++]; } v.push_back(num); } else if(s[i] == '(') { i++; toRPN(s,i,v); } else if(s[i] == ')') { while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } i++; return; } else { if(st.empty() || op[s[i]] > op[st.top()]) { st.push(s[i]); ++i; } else { char ch = st.top(); st.pop(); v.push_back(string(1,ch)); } } } while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } } int evalRPN(vector<string>& tokens) { stack<int> st; int i = 0; map<string,function<int(int,int)>> opFuncMap = { {"+",[](int x,int y){return x + y;}}, {"-",[](int x,int y){return x - y;}}, {"*",[](int x,int y){return x * y;}}, {"/",[](int x,int y){return x / y;}} }; for (auto& str : tokens) { if (opFuncMap.count(str)) { int right = st.top(); st.pop(); int left = st.top(); st.pop(); int ret = opFuncMap[str](left,right); st.push(ret); } else{ st.push(stoi(str)); } } return st.top(); } int calculate(string s) { size_t i = 0; vector<string> v; toRPN(s,i,v); return evalRPN(v); } };这么实现是不行的,因为会存在空格
class Solution { public: map<char,int> op = { {'+',1}, {'-',1}, {'*',2}, {'/',2} }; //中缀转后缀 void toRPN(const string& s,size_t& i,vector<string>& v) { stack<char> st; while(i < s.size()) { if(isdigit(s[i])) { //操作数直接输出 string num; while(i < s.size() && isdigit(s[i])) { num += s[i++]; } v.push_back(num); } else if(s[i] == '(') { i++; toRPN(s,i,v); } else if(s[i] == ')') { while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } i++; return; } else { if(st.empty() || op[s[i]] > op[st.top()]) { st.push(s[i]); ++i; } else { char ch = st.top(); st.pop(); v.push_back(string(1,ch)); } } } while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } } int evalRPN(vector<string>& tokens) { stack<int> st; int i = 0; map<string,function<int(int,int)>> opFuncMap = { {"+",[](int x,int y){return x + y;}}, {"-",[](int x,int y){return x - y;}}, {"*",[](int x,int y){return x * y;}}, {"/",[](int x,int y){return x / y;}} }; for (auto& str : tokens) { if (opFuncMap.count(str)) { int right = st.top(); st.pop(); int left = st.top(); st.pop(); int ret = opFuncMap[str](left,right); st.push(ret); } else{ st.push(stoi(str)); } } return st.top(); } int calculate(string s) { string news; for(auto ch : s) { if(ch != ' ') { news += ch; } } size_t i = 0; vector<string> v; toRPN(news,i,v); return evalRPN(v); } };但是这样还是过不了
如果是(-3)这种,我们将其变成(0-3)
class Solution { public: map<char,int> op = { {'+',1}, {'-',1}, {'*',2}, {'/',2} }; //中缀转后缀 void toRPN(const string& s,size_t& i,vector<string>& v) { stack<char> st; while(i < s.size()) { if(isdigit(s[i])) { //操作数直接输出 string num; while(i < s.size() && isdigit(s[i])) { num += s[i++]; } v.push_back(num); } else if(s[i] == '(') { i++; toRPN(s,i,v); } else if(s[i] == ')') { while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } i++; return; } else { if(st.empty() || op[s[i]] > op[st.top()]) { st.push(s[i]); ++i; } else { char ch = st.top(); st.pop(); v.push_back(string(1,ch)); } } } while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } } int evalRPN(vector<string>& tokens) { stack<int> st; int i = 0; map<string,function<int(int,int)>> opFuncMap = { {"+",[](int x,int y){return x + y;}}, {"-",[](int x,int y){return x - y;}}, {"*",[](int x,int y){return x * y;}}, {"/",[](int x,int y){return x / y;}} }; for (auto& str : tokens) { if (opFuncMap.count(str)) { int right = st.top(); st.pop(); int left = st.top(); st.pop(); int ret = opFuncMap[str](left,right); st.push(ret); } else{ st.push(stoi(str)); } } return st.top(); } int calculate(string s) { string news; for(auto ch : s) { if(ch != ' ') { news += ch; } } news.swap(s); news.clear(); for(size_t i = 0;i < s.size();i++) { if(s[i] == '-' && !isdigit(s[i - 1])) { news += "0-"; } else { news += s[i]; } } cout << news << endl; size_t i = 0; vector<string> v; toRPN(news,i,v); return evalRPN(v); } };但是还是过不了
class Solution { public: map<char,int> op = { {'+',1}, {'-',1}, {'*',2}, {'/',2} }; //中缀转后缀 void toRPN(const string& s,size_t& i,vector<string>& v) { stack<char> st; while(i < s.size()) { if(isdigit(s[i])) { //操作数直接输出 string num; while(i < s.size() && isdigit(s[i])) { num += s[i++]; } v.push_back(num); } else if(s[i] == '(') { i++; toRPN(s,i,v); } else if(s[i] == ')') { while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } i++; return; } else { if(st.empty() || op[s[i]] > op[st.top()]) { st.push(s[i]); ++i; } else { char ch = st.top(); st.pop(); v.push_back(string(1,ch)); } } } while(st.size()) { v.push_back(string(1,st.top())); st.pop(); } } long long evalRPN(vector<string>& tokens) { // 1. 栈类型改为 long long，存储大数避免溢出 stack<long long> st; // 2. 运算函数的参数和返回值都改为 long long map<string, function<long long(long long, long long)>> opFuncMap = { {"+", [](long long x, long long y) { return x + y; }}, {"-", [](long long x, long long y) { return x - y; }}, {"*", [](long long x, long long y) { return x * y; }}, {"/", [](long long x, long long y) { return x / y; }} }; for (auto& str : tokens) { if (opFuncMap.count(str)) { // 3. 弹出的操作数改为 long long long long right = st.top(); st.pop(); long long left = st.top(); st.pop(); // 4. 运算结果改为 long long long long ret = opFuncMap[str](left, right); st.push(ret); } else { // 5. 字符串转数字改用 stoll（转 long long），而非 stoi（转 int） st.push(stoll(str)); } } // 返回栈顶的 long long 结果 return st.top(); } int calculate(string s) { string news; for(auto ch : s) { if(ch != ' ') { news += ch; } } news.swap(s); news.clear(); for(size_t i = 0;i < s.size();i++) { if(s[i] == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] != ')'))) { news += "0-"; } else { news += s[i]; } } cout << news << endl; size_t i = 0; vector<string> v; toRPN(news,i,v); return evalRPN(v); } };还要进行特判,然后用long long代替int,防止我们溢出