C++刷leetcode（面试题 16.26. 计算器）【逆波兰】
本帖最后由 糖逗 于 2020-4-30 15:51 编辑题目描述：
给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
//先将中缀表达式变为后缀表达式
queue<string> trans(string input){
queue<string> res;
map<char, int> store ={{'+',1},{'-',1},{'*',2},{'/',2}};
stack<char> temp;
for(int i = 0; i < input.size(); i++){
if(input >= '0' && input <= '9'){
string total;
while(input >= '0' && input <= '9'){
total += input;
i++;
}
i--;
res.push(total);
}
else if(input == ' ')continue;
else{
if(temp.empty()) temp.push(input);
else if(store] > store){
temp.push(input);
}
else if(store] <= store){//注意这里有等号！！！！
while(!temp.empty() &&store] <= store){
string s(1, temp.top());
res.push(s);
temp.pop();
}
temp.push(input);
}
}
}
if(!temp.empty()){
while(!temp.empty()){
string a(1,temp.top());
res.push(a);
temp.pop();
}
}
queue<string> temp4 = res;
// while(!temp4.empty()){
// cout << temp4.front() << " ";
// temp4.pop();
// }
// cout << endl;
return res;
}
int comput(queue<string> input){
stack<int> temp;
while(!input.empty()){
string cha = input.front();
// cout << cha << endl;
if(temp.empty()){
temp.push(stoi(cha));
}
else if(cha != "+" && cha != "-" && cha != "*" && cha != "/"){
temp.push(stoi(cha));
}
else{
int temp1 = temp.top();
temp.pop();
int temp2 = temp.top();
temp.pop();
int temp3;
if(cha == "*")temp3 = temp1 * temp2;
else if(cha == "-") temp3 = temp2 - temp1;
else if(cha == "+") temp3 = temp1 + temp2;
else if(cha == "/") temp3 = temp2 / temp1;
// cout << temp3 << endl;
temp.push(temp3);
}
input.pop();
}
return temp.top();
}
int calculate(string s) {
int res = 0;
queue<string> temp = trans(s);
res = comput(temp);
return res;
}
注意事项：
1.逆波兰参考《大话数据结构》栈和队列章节内容。 224. 基本计算器
题目描述：实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
示例 1:
输入: "1 + 1"
输出: 2
示例 2:
输入: " 2-1 + 2 "
输出: 3
示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
queue<string> trans(string input){
queue<string> res;
stack<char> temp;
map<char, int> store = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
for(int i = 0; i < input.size(); i++){
if(input == ' ')continue;
else if(input == '(') temp.push(input);
else if(input == ')'){
while(!temp.empty()&&temp.top()!= '('){
string a (1, temp.top());
res.push(a);
temp.pop();
}
temp.pop();
}
else if(input >= '0' && input <= '9'){
string b;
while(i < input.size() &&input >= '0' && input <= '9'){
b+=input;
i++;
}
i--;
res.push(b);
}
else{
if(temp.empty()) temp.push(input);
else if(store] > store) temp.push(input);
else{
while(!temp.empty() && store] <= store){
string c(1, temp.top());
res.push(c);
temp.pop();
}
temp.push(input);
}
}
}
while(!temp.empty()){
string d (1, temp.top());
temp.pop();
res.push(d);
}
// queue<string> temp4 = res;
// while(!temp4.empty()){
// cout << temp4.front() << " ";
// temp4.pop();
// }
// cout << endl;
return res;
}
int comput(queue<string> input){
stack<int> temp;
while(!input.empty()){
string cha = input.front();
if(temp.empty()){
temp.push(stoi(cha));
}
else if(cha != "+" && cha != "-" && cha != "*" && cha != "/"){
temp.push(stoi(cha));
}
else{
int temp1 = temp.top();
temp.pop();
int temp2 = temp.top();
temp.pop();
int temp3;
if(cha == "*")temp3 = temp1 * temp2;
else if(cha == "-") temp3 = temp2 - temp1;
else if(cha == "+") temp3 = temp1 + temp2;
else if(cha == "/") temp3 = temp2 / temp1;
temp.push(temp3);
}
input.pop();
}
return temp.top();
}
int calculate(string s) {
int res = 0;
queue<string> input = trans(s);
res = comput(input);
return res;
}
};
糖逗 发表于 2020-4-30 15:51
224. 基本计算器
题目描述：
C++ 有 eval() 吗？ _2_ 发表于 2020-5-7 11:00
C++ 有 eval() 吗？
貌似是没有{:10_327:}
页:
[1]