问题描述
给定一个算术表达式字符串，只包含 +、-、(、) 、空格和数字，要求算出表达式的值。题目链接：**点我**
样例输入输出
输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23
输入：s = 3- -2
输出：5
问题解法
针对表达式运算，一般都是将中序表达式转成后续表达式，然后结合栈进行求解。本题也不例外，只不过本题中没有乘除的运算，会相对简单一点。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| class Solution
{
public int calculate(String s)
{
Stack<Integer> numStack = new Stack<>();
Stack<Character> opStack = new Stack<>();
int num = 0;
boolean isAddNum = false;
s = s + "#";
for (int i = 0; i < s.length(); i++)
{
char ch = s.charAt(i);
if (ch == ' ')
{
continue;
}
if (Character.isDigit(ch))
{
isAddNum = true;
num = num * 10 + (ch - '0');
continue;
}
if (isAddNum)
{
numStack.push(num);
num = 0;
isAddNum = false;
}
if (ch == '(')
{
opStack.push(ch);
}
else if (ch == ')')
{
while (opStack.peek() != '(')
{
operate(numStack, opStack);
}
opStack.pop();
}
else
{
int index = i - 1;
while (index > 0 && s.charAt(index) == ' ')
{
index--;
}
if (i == 0 || (!Character.isDigit(s.charAt(index)) && s.charAt(index) != ')'))
{
numStack.push(0);
}
while (!opStack.isEmpty() && opStack.peek() != '(')
{
operate(numStack, opStack);
}
opStack.push(ch);
}
}
return numStack.peek();
}
private void operate(Stack<Integer> numStack, Stack<Character> opStack)
{
int second = numStack.pop();
int first = numStack.pop();
char op = opStack.pop();
if (op == '+')
{
numStack.push(first + second);
}
else
{
numStack.push(first - second);
}
}
}
|