手敲栈实现综合计算器
2019-09-18 本文已影响0人
先生zeng
问题: 请入一个字符串表达式，例如: "7+2*4-2/2+3" 然后返回出计算的值。(仅支持加减乘除)
下面是一些需要思考的问题:
1.要计算字符串的值，需要一个个遍历出数字以及符号然后进行计算？因此需要两个栈分别存放
2.计算的顺序需要考虑运算符的优先级问题，因此需要判断运算符的优先级
3.实现的仅仅是简单的个位数的加减乘除，因此不考虑复杂的遍历算法。(这个可以待优化)
4.需要使用栈实现，因此需要自己手动实现一个栈类，对其进行插入和pop出数据。
步骤分析:
要求用栈实现，我们可以看到将字符串中的数字和符号分别遍历的同时存入栈中，然后根据优先级一一计算。具体步骤和思路如图
image
代码实现:
public class Calculator {
public static void main(String[] args) {
String expression = "3+2*3-1";
//创建两个栈，数栈和符号栈
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保存到key
String keepNum = "";
while (true) {
//依次取出expression的每个字符串
ch = expression.substring(index, index + 1).charAt(0);
//判断是数字或符号
if (operStack.isOper(ch)) {
//如果是符号
if (operStack.isEmpty()) {
//如果为空，则符号直接入栈
operStack.add(ch);
} else {
//如果不为null，则进行比较
//如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
//在从符号栈中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.add(res);
//然后将当前的操作符入符号栈
operStack.add(ch);
} else {
//如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
operStack.add(ch);
}
}
} else {
//如果是数，则直接入数栈
numStack.add(ch - 48); ***** 标注1
}
index++;
if (index >= expression.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.add(res);
}
//将数栈的最后数，pop出，就是结果
System.out.println("表达式是:"+ expression +"===" + numStack.pop());
}
static class ArrayStack {
private final int INIT_TOP_VALUE = -1;
//栈大小
private int maxSize;
//存放数据
private int[] stack;
//栈顶
private int top;
public ArrayStack(int maxSize){
this.top = INIT_TOP_VALUE;
this.maxSize = maxSize;
this.stack = new int[maxSize];
}
/**
* 返回当前栈顶的值，但是不真正pop
*/
public int peek(){
return this.stack[top];
}
/**
* 返回运算符的优选级，优先级使用数字表示
* @return
*/
public int priority(int oper){
if(oper == '*' || oper == '/'){
return 1;
} else if(oper == '+' || oper == '-'){
return 0;
} else {
return -1;
}
}
/**
* 判断是否是一个运算符
* @param val
* @return
*/
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;
}
/**
* 判断栈是否为null
*/
private Boolean isEmpty(){
return top == -1;
}
/**
* 判断栈是否为满
*/
private Boolean isFull(){
return this.top == this.maxSize - 1;
}
/**
* 入栈
*/
public void add(int val){
if(isFull()){
throw new RuntimeException("栈满");
}
this.stack[++this.top] =val;
}
/**
* 出栈
*/
public int pop(){
if(isEmpty()){
throw new RuntimeException("当前栈没有元素，不能出栈");
}
return this.stack[this.top--];
}
/**
* 遍历
*/
public void getArrayStack(){
if(isEmpty()) {
System.out.println("当前栈没有元素，打印为null");
return ;
}
for(int i = top; i >= 0; i--) {
System.out.println("stack["+i+"]="+this.stack[i]);
}
}
}
}
运行结果:
image
下面我们可以思考下：如何实现多位数的计算:
优化:
image
我们可以看到，在遍历时，如果发现是数，我们是直接入栈的，没有考虑多位数的情况。因此在这里进行优化。
我们需要新增一个变量:
image
然后在上面代码行有一个标注一的那一行，或者说，在计算思路第二步的处理逻辑那里，改成如下代码:
将圈起部分替换成如下面的:
image
//numStack.push(ch - 48); //? "1+3" '1' => 1
//分析思路
//1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
//2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
//3. 因此我们需要定义一个变量 字符串，用于拼接
//处理多位数
keepNum += ch;
//如果ch已经是expression的最后一位，就直接入栈
if (index == expression.length() - 1) {
numStack.add(Integer.parseInt(keepNum));
}else{
//判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
//注意是看后一位，不是index++
if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
//如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
numStack.add(Integer.parseInt(keepNum));
//重要的!!!!!!, keepNum清空
keepNum = "";
}
}
运算结果:
image
完成！
