C++刷leetcode（面试题 16.26. 计算器）【逆波兰】

糖逗

题目描述：

1. 
   
2. 给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
   
3. 
   
4. 表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。
   
5. 
   
6. 示例 1:
   
7. 
   
8. 输入: "3+2*2"
   
9. 输出: 7
   
10. 示例 2:
    
11. 
    
12. 输入: " 3/2 "
    
13. 输出: 1
    
14. 示例 3:
    
15. 
    
16. 输入: " 3+5 / 2 "
    
17. 输出: 5
    
18. 说明：
    
19. 
    
20. 你可以假设所给定的表达式都是有效的。
    
21. 请不要使用内置的库函数 eval。

复制代码

1.     //先将中缀表达式变为后缀表达式
   
2.     queue<string> trans(string input){
   
3.         queue<string> res;
   
4.         map<char, int> store ={{'+',1},{'-',1},{'*',2},{'/',2}};
   
5.         stack<char> temp;
   
6.         for(int i = 0; i < input.size(); i++){
   
7.             if(input[i] >= '0' && input[i] <= '9'){
   
8.                 string total;
   
9.                 while(input[i] >= '0' && input[i] <= '9'){
   
10.                     total += input[i];
    
11.                     i++;
    
12.                 }
    
13.                 i--;
    
14.                 res.push(total);
    
15.             }
    
16.             else if(input[i] == ' ')continue;
    
17.             else{
    
18. 
    
19.                 if(temp.empty()) temp.push(input[i]);
    
20.                 else if(store[input[i]] > store[temp.top()]){
    
21.                     temp.push(input[i]);
    
22.                 }
    
23.                 else if(store[input[i]] <= store[temp.top()]){//注意这里有等号！！！！
    
24.                     while(!temp.empty() &&store[input[i]] <= store[temp.top()]){  
    
25.                         string s(1, temp.top());      
    
26.                         res.push(s);
    
27.                         temp.pop();
    
28.                     }
    
29.                     temp.push(input[i]);
    
30.                 }
    
31.             }
    
32.         }
    
33.         if(!temp.empty()){
    
34.             while(!temp.empty()){
    
35.                 string a(1,temp.top());
    
36.                 res.push(a);
    
37.                 temp.pop();
    
38.             }
    
39.         }
    
40.         queue<string> temp4 = res;
    
41.         // while(!temp4.empty()){
    
42.         //     cout << temp4.front() << " ";
    
43.         //     temp4.pop();
    
44.         // }
    
45.         // cout << endl;
    
46.         return res;
    
47.     }
    
48.     int comput(queue<string> input){
    
49.         stack<int> temp;
    
50.         while(!input.empty()){
    
51.             string cha = input.front();
    
52.             // cout << cha << endl;
    
53.             if(temp.empty()){
    
54.                 temp.push(stoi(cha));
    
55.             }
    
56.             else if(cha != "+" && cha != "-" && cha != "*" && cha != "/"){
    
57.                 temp.push(stoi(cha));
    
58.             }
    
59.             else{
    
60.                 int temp1 = temp.top();
    
61.                 temp.pop();
    
62.                 int temp2 = temp.top();
    
63.                 temp.pop();
    
64.                 int temp3;
    
65.                 if(cha == "*")  temp3 = temp1 * temp2;
    
66.                 else if(cha == "-") temp3 = temp2 - temp1;
    
67.                 else if(cha == "+") temp3 = temp1 + temp2;
    
68.                 else if(cha == "/") temp3 = temp2 / temp1;
    
69.                 // cout << temp3 << endl;
    
70.                 temp.push(temp3);
    
71.                
    
72.             }
    
73.             input.pop();
    
74.         }
    
75.         return temp.top();
    
76.     }
    
77.     int calculate(string s) {
    
78.         int res = 0;
    
79.         queue<string> temp = trans(s);
    
80.         res = comput(temp);
    
81.         return res;
    
82. 
    
83.     }

复制代码

注意事项：
1.逆波兰参考《大话数据结构》栈和队列章节内容。

糖逗

224. 基本计算器
题目描述：

1. 实现一个基本的计算器来计算一个简单的字符串表达式的值。
   
2. 
   
3. 字符串表达式可以包含左括号&#160;(&#160;，右括号&#160;)，加号&#160;+&#160;，减号&#160;-，非负整数和空格&#160;&#160;。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: "1 + 1"
   
8. 输出: 2
   
9. 示例 2:
   
10. 
    
11. 输入: " 2-1 + 2 "
    
12. 输出: 3
    
13. 示例 3:
    
14. 
    
15. 输入: "(1+(4+5+2)-3)+(6+8)"
    
16. 输出: 23
    
17. 说明：
    
18. 
    
19. 你可以假设所给定的表达式都是有效的。
    
20. 请不要使用内置的库函数 eval。
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/basic-calculator
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     queue<string> trans(string input){
   
4.         queue<string> res;
   
5.         stack<char> temp;
   
6.         map<char, int> store = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
   
7.         for(int i = 0; i < input.size(); i++){
   
8.             if(input[i] == ' ')continue;
   
9.             else if(input[i] == '(') temp.push(input[i]);
   
10.             else if(input[i] == ')'){
    
11.                 while(!temp.empty()&&temp.top()!= '('){
    
12.                     string a (1, temp.top());
    
13.                     res.push(a);
    
14.                     temp.pop();
    
15.                 }
    
16.                 temp.pop();
    
17.             }
    
18.             else if(input[i] >= '0' && input[i] <= '9'){
    
19.                 string b;
    
20.                 while(i < input.size() &&input[i] >= '0' && input[i] <= '9'){
    
21.                     b+=input[i];
    
22.                     i++;
    
23.                 }
    
24.                 i--;
    
25.                 res.push(b);
    
26.             }
    
27.             else{
    
28.                 if(temp.empty()) temp.push(input[i]);
    
29.                 else if(store[input[i]] > store[temp.top()]) temp.push(input[i]);
    
30.                 else{
    
31.                     while(!temp.empty() && store[input[i]] <= store[temp.top()]){
    
32.                         string c(1, temp.top());
    
33.                         res.push(c);
    
34.                         temp.pop();
    
35.                     }
    
36.                     temp.push(input[i]);
    
37.                 }
    
38. 
    
39.             }
    
40.         }
    
41.         while(!temp.empty()){
    
42.             string d (1, temp.top());
    
43.             temp.pop();
    
44.             res.push(d);
    
45.         }
    
46.         // queue<string> temp4 = res;
    
47.         // while(!temp4.empty()){
    
48.         //     cout << temp4.front() << " ";
    
49.         //     temp4.pop();
    
50.         // }
    
51.         // cout << endl;
    
52.         return res;
    
53.     }
    
54. 
    
55.     int comput(queue<string> input){
    
56.         stack<int> temp;
    
57.         while(!input.empty()){
    
58.             string cha = input.front();
    
59.             if(temp.empty()){
    
60.                 temp.push(stoi(cha));
    
61.             }
    
62.             else if(cha != "+" && cha != "-" && cha != "*" && cha != "/"){
    
63.                 temp.push(stoi(cha));
    
64.             }
    
65.             else{
    
66.                 int temp1 = temp.top();
    
67.                 temp.pop();
    
68.                 int temp2 = temp.top();
    
69.                 temp.pop();
    
70.                 int temp3;
    
71.                 if(cha == "*")  temp3 = temp1 * temp2;
    
72.                 else if(cha == "-") temp3 = temp2 - temp1;
    
73.                 else if(cha == "+") temp3 = temp1 + temp2;
    
74.                 else if(cha == "/") temp3 = temp2 / temp1;
    
75.                 temp.push(temp3);
    
76.                
    
77.             }
    
78.             input.pop();
    
79.         }
    
80.         return temp.top();
    
81.     }
    
82. 
    
83.     int calculate(string s) {
    
84.         int res = 0;
    
85.         queue<string> input = trans(s);
    
86.         res = comput(input);
    
87.         return res;
    
88. 
    
89.     }
    
90. };

复制代码

_2_

糖逗 发表于 2020-4-30 15:51
224. 基本计算器
题目描述：

C++ 有 eval() 吗？

糖逗

_2_ 发表于 2020-5-7 11:00
C++ 有 eval() 吗？

貌似是没有