题解 | #表达式求值#
表达式求值
http://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
题目的主要信息：
- 写一个支持+ - *三种符号的运算器，其中优先级+ - 是一级，*更高一级
- 支持括号运算
举一反三：
方法：栈 + 递归（推荐使用）
知识点：栈
栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
思路：
对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。
处理优先级问题，那必定是乘号有着优先运算的权利，加号减号先一边看，我们甚至可以把减号看成加一个数的相反数，则这里只有乘法和加法，那我们优先处理乘法，遇到乘法，把前一个数和后一个数乘起来，遇到加法就把这些数字都暂时存起来，最后乘法处理完了，就剩余加法，把之前存起来的数字都相加就好了。
处理括号的问题，我们可以将括号中的部分看成一个新的表达式，即一个子问题，因此可以将新的表达式递归地求解，得到一个数字，再运算：
- 终止条件： 每次遇到左括号意味着进入括号子问题进行计算，那么遇到右括号代表这个递归结束。
- 返回值： 将括号内部的计算结果值返回。
- 本级任务： 遍历括号里面的字符，进行计算。
具体做法：
- step 1：使用栈辅助处理优先级，默认符号为加号。
- step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
- step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
- step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
- step 5：最后将栈中剩余的所有元素，进行一次全部相加。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public ArrayList<Integer> function(String s, int index){
Stack<Integer> stack = new Stack<Integer>();
int num = 0;
char op = '+';
int i;
for(i = index; i < s.length(); i++){
//数字转换成int数字
//判断是否为数字
if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
num = num * 10 + s.charAt(i) - '0';
if(i != s.length() - 1)
continue;
}
//碰到'('时，把整个括号内的当成一个数字处理
if(s.charAt(i) == '('){
//递归处理括号
ArrayList<Integer> res = function(s, i + 1);
num = res.get(0);
i = res.get(1);
if(i != s.length() - 1)
continue;
}
switch(op){
//加减号先入栈
case '+':
stack.push(num);
break;
case '-':
//相反数
stack.push(-num);
break;
//优先计算乘号
case '*':
int temp = stack.pop();
stack.push(temp * num);
break;
}
num = 0;
//右括号结束递归
if(s.charAt(i) == ')')
break;
else
op = s.charAt(i);
}
int sum = 0;
//栈中元素相加
while(!stack.isEmpty())
sum += stack.pop();
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(sum);
temp.add(i);
return temp;
}
public int solve (String s) {
ArrayList<Integer> res = function(s, 0);
return res.get(0);
}
}
C++实现代码：
class Solution {
public:
vector<int> function(string s, int index){
stack<int> stack;
int num = 0;
char op = '+';
int i;
for(i = index; i < s.length(); i++){
//数字转换成int数字
if(isdigit(s[i])){
num = num * 10 + s[i] - '0';
if(i != s.length() - 1)
continue;
}
//碰到'('时，把整个括号内的当成一个数字处理
if(s[i] == '('){
//递归处理括号
vector<int> res = function(s, i + 1);
num = res[0];
i = res[1];
if(i != s.length() - 1)
continue;
}
switch(op){
//加减号先入栈
case '+':
stack.push(num);
break;
case '-':
//相反数
stack.push(-num);
break;
//优先计算乘号
case '*':
int temp = stack.top();
stack.pop();
stack.push(temp * num);
break;
}
num = 0;
//右括号结束递归
if(s[i] == ')')
break;
else
op = s[i];
}
int sum = 0;
//栈中元素相加
while(!stack.empty()){
sum += stack.top();
stack.pop();
}
return vector<int> {sum, i};
}
int solve(string s) {
return function(s, 0)[0];
}
};
Python代码实现：
class Solution:
def solve(self , s ):
s = s.strip()
stack = []
res = 0
num = 0
sign = '+'
index = 0
while index < len(s):
if s[index] == ' ':
index += 1
continue
# 遇到左括号
if s[index] == '(':
end = index + 1
lens = 1
while lens > 0:
if s[end] == '(':
lens += 1
if s[end] == ')':
lens -= 1
end += 1
#将括号视为子问题进入递归
num = self.solve(s[index + 1: end - 1])
index = end - 1
continue
#字符数字转换成int数字
if '0' <= s[index] <= '9':
num = num * 10 + int(s[index])
#根据符号运算
if not '0' <= s[index] <= '9' or index == len(s) - 1:
#加
if sign == '+':
stack.append(num)
#减，加相反数
elif sign == '-':
stack.append(-1 * num)
#乘优先计算
elif sign == '*':
stack.append(stack.pop() * num)
num = 0
sign = s[index]
index += 1
#栈中元素相加
while stack:
res += stack.pop()
return res
复杂度分析：
- 时间复杂度：，为字符串长度，相当于遍历一遍字符串全部元素
- 空间复杂度：，辅助栈和递归栈的空间
投递金山WPS等公司10个岗位 >
