一.带括号的数学表达式求值。

题目描述

请写一个整数计算器,支持加减乘三种运算和括号。

示例1

输入
1
"(2*(3-4))*5"
返回值
1
-10

示例2

输入
1
"3+2*3*4-1"
返回值
1
26

解法1:

  • 1.用栈保存各部分计算的和
  • 2.遍历表达式,使用 sign 变量记录运算符,初始化是 ‘+’;使用 number 变量记录字符串中的数字部分的数字值是多少
    • 2.0 遇到空格时跳过
    • 2.1 遇到数字时继续遍历求这个完整的数字的值,保存到 number 中
    • 2.2 遇到左括号时递归求这个括号里面的表达式的值
      • 先遍历找到对应的右括号,因为可能里面还嵌有多对括号,使用一个变量 count 统计括号对数直到变量为 0
    • 2.3 遇到运算符时或者到表达式末尾时,就去计算上一个运算符并把计算结果 push 进栈,然后保存新的运算符到 sign
      • 如果是 + ,不要计算,push 进去
      • 如果是 - ,push 进去负的当前数
      • 如果是 ×、÷ ,pop 出一个运算数和当前数作计算
  • 3.最后把栈中的结果求和即可
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
import java.util.*;
public class Solution {
public int solve (String s) {
LinkedList<Integer> stack= new LinkedList<>();
char sign='+';
int num=0;
char[] chars=s.toCharArray();
int len=s.length(),i=0;
for(i=0;i<chars.length;i++){
char temp=chars[i];
if(Character.isDigit(temp)) num=num*10+(temp-'0');
if(temp=='('){
int left=i,right=i+1;
int count=1;
while(count>0){
if(chars[right]=='(')count++;
if(chars[right]==')')count--;
right++;
}
num=solve(s.substring(left+1,right-1));//递归求括号内的值
i=right-1;
}
if(!Character.isDigit(temp)||i==len-1){
if(sign=='+')stack.push(num);
if(sign=='-')stack.push(-1*num);
if(sign=='*')stack.push(stack.pop()*num);
sign=temp;
num=0;
}
}
int res=0;
while(!stack.isEmpty())res=res+stack.pop();
return res;
}
}