给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中，均不超过 231−1。
题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。
输入格式
共一行，为给定表达式。
输出格式
共一行，为表达式的结果。
数据范围
表达式的长度不超过105。
输入样例：
(2+2)*(1+1)
输出样例：
8
对于这道题，我们可以使用两个栈，一个栈nums用来存运算数，另外一个栈ops可以用来存运算符，但是运算符之间是存在优先级的，我们还可以使用一个哈希表来储存每个运算符的优先级，可以使用数字的大小表示优先级的高低。
第一步，遍历字符串，可能会遇到以下情况：
1）遇到数字，将数组储存到栈nums中。
2）遇到（，直接将（存到栈ops中。
3）遇到），取出栈顶两个数，取出栈顶运算符，进行运算，将运算结果存入栈nums中，如果栈ops栈顶不为空并且栈顶元素不为（，则继续运算，直到栈为空或者栈顶元素为（为止。
4）遇到运算符+，-，*，/，检查栈ops栈顶运算符优先级是否大于或等于遍历遇到的运算符，如果优先级大，则进行运算操作（同上取出栈nums两个数，栈ops一个操作符进行运算，并将结果储存到nums中），然后继续检查，直到栈ops为空或者ops栈顶元素为（，最后将遍历的运算符入栈ops。
第二步，检查是否运算完成。
字符串遍历完成后，此时运算不一定结束，检查栈ops是否为空，不为空继续进行运算操作，直到栈ops为空为止，最终nums剩余的一个数就是运算结果。
对于运算符优先级的判断我们可以通过建立哈希表，将运算符映射一个数字，其中数字越大就表示优先级越大。
Java版本实现：
import java.util.*;
class Main {
//栈nums 存运算数
private static Deque<Integer> nums = new ArrayDeque<>();
//栈ops 存运算符
private static Deque<Character> ops = new ArrayDeque<>();
//哈希表用来映射运算符优先级
private static HashMap<Character, Integer> hash = new HashMap<>();
//初始化哈希表
static {
hash.put('+', 1);
hash.put('-', 1);
hash.put('*', 2);
hash.put('/', 2);
}
//判断某个字符是否是数字
private static boolean isDigit(char c) {
return c >= '0' &&c <= '9';
}
//实现运算方法
private static void eval() {
//去除第二个运算数
int b = nums.pollLast();
//取出第一个运算数
int a = nums.pollLast();
//取出运算符
char op = ops.pollLast();
//判断符号，对应进行运算
if (op == '+') nums.offerLast(a + b);
else if (op == '-') nums.offerLast(a - b);
else if (op == '*') nums.offerLast(a * b);
else if (op == '/') nums.offerLast(a / b);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; i++) {
char c = cs[i];
if (isDigit(c)) {
//遍历的字符为数字，取出完整的数字放在数组当中
int ret = c - '0';
int j = i + 1;
while (j < cs.length && isDigit(cs[j])) {
ret = ret * 10 + (cs[j] - '0');
j++;
}
//更新i
i = j - 1;
//将数字入栈
nums.offerLast(ret);
} else if (c == '(') {
//遇到(，直接入栈ops
ops.offerLast(c);
} else if (c == ')') {
//遇到)，进行运算操作，直到栈顶遇到(为止
while (!ops.isEmpty() && ops.peekLast() != '(') eval();
//遇到(，将(出栈
ops.pollLast();
} else {
//遇到运算符，则比较优先级，如栈顶运算符优先级大，则进行运算，直到栈为空或栈顶运算符较小或栈顶运算符为(
while (!ops.isEmpty() && ops.peekLast() != '(' && hash.get(ops.peekLast()).compareTo(hash.get(c)) >= 0) eval();
//将当前运算符入栈
ops.offerLast(c);
}
}
//检查ops栈内是否还有运算符，如果还有，则表示运算还没结束，继续运算，直到ops栈无运算符为止
while (!ops.isEmpty()) eval();
//输出nums栈顶元素，即是最终运算结果
System.out.println(nums.peekLast());
}
}
C++版本实现：
include <iostream>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <string>
using namespace std;
//栈1 存储元素
stack<int> nums;
//栈2 存储操作符号
stack<char> ops;
//哈希表 用来存储运算符优先级
unordered_map<char, int> pri = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
void eval()
{
//取第二个操作数
int b = nums.top();
nums.pop();
//取第一个操作数
int a = nums.top();
nums.pop();
//取操作符
char op = ops.top();
ops.pop();
//进行运算
if (op == '+') nums.push(a + b);
else if (op == '-') nums.push(a - b);
else if (op == '*') nums.push(a * b);
else if (op == '/') nums.push(a / b);
//cout << a << " " << op << " " << b << "=";
//cout << nums.top() << endl;
}
int main()
{
string s;
cin >> s;
for (int i = 0; i < s.size(); i++)
{
char c = s[i];
if (isdigit(c))
{
//字符为数字，将该数字放入到储存数字的栈中
int j = i + 1;
int ret = s[i] - '0';
while (j < s.size() && isdigit(s[j]))
{
ret = ret * 10 + (s[j] - '0');
j++;
}
//更新i
i = j - 1;
nums.push(ret);
} else if (c == '(')
{
ops.push(c);
} else if (c == ')')
{
//遇到右括号对栈元素进行运算，直到遇到(为止
while (ops.size() > 0 && ops.top() != '(') eval();
ops.pop();
} else {
//遇到运算符，比较优先级，如果优先级较高，则进行运算
while (ops.size() > 0 && ops.top() != '(' && pri[ops.top()] >= pri[c]) eval();
ops.push(c);
}
}
//如果还有剩余运算符 则继续运算
while (ops.size() > 0) eval();
//栈顶元素即为最终的运算结果
cout << nums.top() << endl;
return 0;
}
