支线任务2Basic Calculator

问题描述：

题目要求我们实现一个简单的加减计算器，计算一个表达式的值，表达式除了数字之外还可能会含有括号，加减符号以及空格。

思路：

其实看到这个题自然就会想到利用后缀式求表达式值的算法作业题，况且这个题还没有乘法除法运算，我就沿用了做算法作业题的思路来求解：

1.由原表达式求出后缀式

2.根据后缀式求值

当然，这个题由于没有乘除法，不需要考虑运算符的优先性而只需要考虑括号的分隔作用，相比于算法作业有很多地方可以简化：比如新的一个运算符号遇到栈顶符号时可以直接拿出栈顶符号，又比如在栈里在'('之上的至多只有一个符号。

具体解决方案：

1.利用一个char逐个读取string s里的字符，并作判断，若为空格不做操作；

2.利用一个字符栈进行后缀式求解，左扩号直接进栈；加减符号若遇栈顶同为加减号则退出栈顶符号加到后缀式，新符号进栈；右括号若遇栈顶为左括号则直接把左括号退出栈顶，否则退出运算符加入后缀式，再退出左括号；

3.数与数之间用'$'分隔开以便后缀式的计算，例:"$13$24"；

4.用一个<int>栈计算后缀式的值，读取到表达式里面的数值则存入栈，遇到符号则对栈顶和栈顶下一位的数值进行相应的计算并把结果存在栈顶；

5.返回栈顶数值。

相应的代码：

 1 class Solution {
 2 public:
 3     int calculate(string s) {
 4         stack<char> operation;
 5     stack<int> numCan;
 6     string newExp, temNumExp;
 7     char temsave;
 8     int temTop, temNum;
 9     bool isNextNum = true;
10     istringstream iss;
11     for(int i = 0;i < s.size();i++)//求得后缀式
12     {
13         temsave = s[i];
14         if(temsave != ' ')
15         {
16             if(temsave >= '0' && temsave <= '9')
17             {
18                 if(isNextNum == true)
19                 {
20                     newExp += '$';//$分隔两个数
21                     newExp += temsave;
22                     isNextNum = false;
23                 }
24                 else
25                     newExp += temsave;
26             }
27             else
28             {
29                 isNextNum = true;
30                 if(temsave == '+' || temsave == '-')
31                 {
32                     if(operation.empty() == true || operation.top() == '(')
33                         operation.push(temsave);
34                     else
35                     {
36                         newExp += operation.top();
37                         operation.pop();
38                         operation.push(temsave);
39                     }
40                 }
41                 else if(temsave == '(')
42                     operation.push(temsave);
43                 else
44                 {
45                     if(operation.top() != '(')
46                     {
47                         newExp += operation.top();
48                         operation.pop();
49                         operation.pop();
50                     }
51                     else
52                         operation.pop();
53                 }
54             }
55         }
56     }
57     if(operation.empty() == false)
58         newExp += operation.top();
59     for(int i = 0;i < newExp.size();i++)//计算后缀式
60     {
61         temsave = newExp[i];
62         if(temsave == '+' || temsave == '-')
63         {
64             temTop = numCan.top();
65             numCan.pop();
66             if(temsave == '+')
67                 numCan.top() += temTop;
68             else
69                 numCan.top() -= temTop;
70         }
71         else if(temsave == '$')
72         {
73             i++;
74             iss.clear();
75             while(newExp[i] != '+' && newExp[i] != '-' && newExp[i] != '$' && i < newExp.size())
76             {
77                 temNumExp += newExp[i];
78                 i++;
79             }
80             i--;
81             iss.str(temNumExp);
82             iss >> temNum;
83             numCan.push(temNum);
84             temNumExp = "";
85         }
86     }
87     return  numCan.top();
88     }
89 };

运行结果：

时间好长╮(╯▽╰)╭，然而没有时间改进了……