如下图
根据用户输入的表达式,得出计算结果
本题看似简单,实则不然,要实现这个功能我们不能简单的直接将这个字符串丢给程序 如下
int a = 7*2*2-5+1-5*3-3 // 3
我们要模拟计算机是如何解析,并计算出这样一个字符串的结果。
如果我们自己实现这样一个功能,至少会涉及到,数字拆分、运算符解析、运算符优先级计算。 这里就可以利用栈先入后出的特点完成该程序
大体思路如下
首先创建两个栈—-数字栈和符号栈
1.通过一个index
值(索引)来遍历表达式
2.当遍历的元素是数字时,将其放入数字栈中
3.当遍历的元素是符号时,就分为如下情况
3.1 如果发现当前的符号栈为空,就直接入符号栈
3.2 当前的符号栈不为空,要进行比比较
3.2.1如果当前的符号的优先级小于或等于栈顶中的符号。就需要从数栈中pop
出两个数,在从符号栈中pop
出一个符号,并进行运算,将得到的结果放入数栈,在将当前符号放入符号栈
3.2.2 如果当前的符号的优先级大于栈顶中的符号。则直接入符号栈
4.当表达式遍历完毕时,就顺序的从数栈和符号栈中pop出相应的数和符号,并进行运算
5.最后数栈中只有一个数字,即最后的结果
图示
如下例计算 3+2*6-2
第一次扫描时,发现是数字,将其放入数栈中。
第二次扫描时,发现是符号,并且当前符号栈为空,所以直接放入符号栈
第三次扫描时,发现是数字,将其放入数栈中
第四次扫描时,发现是符号(*
),并且当前符号的优先级是大于符号栈,栈顶符号的优先级的。此时直接入符号栈
第五次扫描时,发现是数字,直接放入数字栈中
第六次扫描发现是符号(-
),并且当前符号的优先级是小于栈顶符号(*
)的优先级,此时在数栈中弹出两个数(6和2
),符号栈中弹出一个符号(*
),将它们进行运算得到结果12
,并将结果放入数栈中,同时将当前符号(-
)放入到符号栈中
第七次扫描,发现是数字,直接将其放入数栈中
此时已经遍历完毕,接下来要将数栈和符号栈中的元素分别弹出进行运算 第一次弹出 12和2和-
运算得到结果为10,并将其放入数栈中
此时,在弹出数栈和符号栈中的元素 10和3和+
,得到运算结果为13,将其放入数栈中 此时数栈中只有一个元素即表达式运算的结果
首先用数组模拟栈,创建一个栈类
class ArrayStack{
private int maxSize;
private int[] stack; //栈数组
private int top = -1; //栈顶
public ArrayStack(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
//判断栈是否满
public boolean isFull(){
return top == maxSize - 1;
}
//栈是否为空
public boolean isEmpty(){
return top == -1;
}
//入栈
public void push(int value){
if(isFull()){
System.out.println("栈已满,不能放");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
int value = stack[top];
top--;
return value;
}
//显示栈中的元素
public void list(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
//从栈顶开始显示数据
for(int i = top ; i >= 0 ;i--){
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
为了后面方便计算,我们还得给栈添加几个方法 1.查看栈顶中的元素 2.计算符号优先级 3.判断是否为运算符 4.计算方法
...
//查看栈顶的元素,而不是弹出
public int peek(){
return stack[top];
}
//返回运算符优先级,数字越大优先级越高
public int priority(int oper){
if(oper == '*' || oper == '/'){
return 1;
}else if (oper == '+' || oper == '-'){
return 0;
}else{
return -1;
}
}
//判断是否为运算符
public boolean isOper(char val){
return val == '+' || val == '-' || val == '*' || val == '/';
}
//计算
public int cal(int num1,int num2, int oper){
int res = 0; //计算的结果
switch (oper){
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}
接下来完成我们的程序
public static void main(String[] args) {
//运算的表达式
String expr = "3+2*6-2";
//创建数栈和符号栈
ArrayStack numStack = new ArrayStack(10);
ArrayStack operStack = new ArrayStack(10);
int index = 0; //用于遍历表达式
int num1 = 0;
int num2 = 0;
int oper = 0; //运算符
int res = 0; //运算后的结果
char ch = ' '; //将每次扫描得到的char保存到ch
//while循环扫描表达式
while (true){
//依次扫描expr
ch = expr.substring(index,index+1).charAt(0);
//判断 ch 是数字还是符号
if(operStack.isOper(ch)){
//ch是运算符
if(operStack.isEmpty()){
//如果符号栈为空则直接入栈
operStack.push(ch);
}else{
/*符号栈不为空
判断符号的优先级是否大于栈顶符号的优先级
直接放入符号栈顶
判断符号的优先级是否小于等于栈顶符号的优先级
从数栈pop两个数,并和栈顶符号运算
*/
if(operStack.priority(ch) <= operStack.priority(operStack.peek())){
//进行运算
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1,num2,oper);
numStack.push(res); //将运算的结果入数栈
operStack.push(ch); //并将当前的符号入符号栈
}else{
//符号的优先级是否大于栈顶符号的优先级,直接入栈
operStack.push(ch);
}
}
}else{
//不是符号,认为是数字,直接放入数栈
// 需要将字符转换为数字 如 '1' ==> 1
// 字符数字 与 整形数字刚好相差 48
// 如 '1'转换为十进制为49
numStack.push(ch - 48);
}
index ++;
//扫描到最后退出循环
if(index >= expr.length()){
break;
}
}
//当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号进行计算
while (true){
//当符号栈为空时,说明计算到最后的结果了,数栈中只有一个数字即结果
if(operStack.isEmpty()){
break;
}
//进行运算
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1,num2,oper);
numStack.push(res); //将运算的结果入数栈
}
//将数栈的最后一个元素pop出来,即最后的结果
System.out.printf("表达式 %s = %d",expr,numStack.pop());
}
测试得到结果如下
表达式 3+2*6-2 = 13
可以看到结果和我们预期的一样,但是目前我们的程序还有问题
如果我们把表达式改成
expr = "30+2*6-2";
最后输出结果为
表达式 3+2*6-2 = 10
显然结果不对,这里就涉及到如何解决多位数的问题
问题就在在段代码中
...
else{
//不是符号,认为是数字,直接放入数栈
// 需要将字符转换为数字 如 '1' ==> 1
// 字符数字 与 整形数字刚好相差 48
// 如 '1'转换为十进制为49
numStack.push(ch - 48);
}
...
我们直接将数放入栈中了,没有考虑到多为数的问题
解决这个问题的思路如下 1.在处理数字时,不能一发现数字就立即入栈 2.在处理数字时,需要向表达式的index后移一位,如果是数字则继续扫描,如果是符号才入栈 3.我们需要定义一个变量字符串,用于拼接拼接多为数
...
int num1 = 0;
int num2 = 0;
int oper = 0; //运算符
int res = 0; //运算后的结果
char ch = ' '; //将每次扫描得到的char保存到ch
String keepNum = "";//用于拼接多位数
...
...
else{
//不是符号,认为是数字,直接放入数栈
// 需要将字符转换为数字 如 '1' ==> 1
// 字符数字 与 整形数字刚好相差 48
// 如 '1'转换为十进制为49
//处理多位数问题
keepNum += ch;
//如果 ch 是 表达式的最后一位则直接入栈
if(index == expr.length() - 1){
numStack.push(Integer.parseInt(keepNum));
}else{
//判断 ch 下一个字符是否为符号,如果是直接入栈
if(operStack.isOper(expr.substring(index+1,index+2).charAt(0))){
numStack.push(Integer.parseInt(keepNum));
keepNum = "";//清空keepNum
}
}
}
...
再次运行得到正确的结果
表达式 30+2*6-2 = 40