一.计算器实现思路二.分析这里我们要将后缀表达式,转换成为中缀表达式建立一个栈存储运算数读取后缀表达式遇到运算数入栈遇到运算符出栈顶两个数进行运算运算后将结果作为一个运算数入栈继续参与下一次的运算。读取表达式结束后最后栈顶的数值就是运算结果。三.中缀表达式转后缀表达式四.代码实现#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream #includeset #includemap #includestring #includevector #includestack using namespace std; class Solution { public: mapchar,int op { {,1}, {-,1}, {*,2}, {/,2} }; //中缀转后缀 void toRPN(const string s,size_t i,vectorstring v) { stackchar 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; vectorstring v; //string str 12-3; string str 12-(3*45)-7; Solution().toRPN(str, i, v); for (auto e : v) { cout e ; } cout endl; return 0; }五.题目题目链接:224. 基本计算器 - 力扣LeetCode题目链接:1.先将逆波兰表达式求值这个代码写出来class Solution { public: int evalRPN(vectorstring tokens) { stackint st; int i 0; mapstring,functionint(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: mapchar,int op { {,1}, {-,1}, {*,2}, {/,2} }; //中缀转后缀 void toRPN(const string s,size_t i,vectorstring v) { stackchar 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(vectorstring tokens) { stackint st; int i 0; mapstring,functionint(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; vectorstring v; toRPN(s,i,v); return evalRPN(v); } };这么实现是不行的,因为会存在空格class Solution { public: mapchar,int op { {,1}, {-,1}, {*,2}, {/,2} }; //中缀转后缀 void toRPN(const string s,size_t i,vectorstring v) { stackchar 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(vectorstring tokens) { stackint st; int i 0; mapstring,functionint(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; vectorstring v; toRPN(news,i,v); return evalRPN(v); } };但是这样还是过不了如果是(-3)这种,我们将其变成(0-3)class Solution { public: mapchar,int op { {,1}, {-,1}, {*,2}, {/,2} }; //中缀转后缀 void toRPN(const string s,size_t i,vectorstring v) { stackchar 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(vectorstring tokens) { stackint st; int i 0; mapstring,functionint(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; vectorstring v; toRPN(news,i,v); return evalRPN(v); } };但是还是过不了class Solution { public: mapchar,int op { {,1}, {-,1}, {*,2}, {/,2} }; //中缀转后缀 void toRPN(const string s,size_t i,vectorstring v) { stackchar 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(vectorstring tokens) { // 1. 栈类型改为 long long存储大数避免溢出 stacklong long st; // 2. 运算函数的参数和返回值都改为 long long mapstring, functionlong 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; vectorstring v; toRPN(news,i,v); return evalRPN(v); } };还要进行特判,然后用long long代替int,防止我们溢出