数据结构（Java）——栈实现简单计算器

利用栈实现简单的计算器

具体思路

1.通过一个index值(索引)，来遍历我们的表达式
2.如果我们发现是一个数字,就直接入数栈
3.如果发现扫描到是一个符号，就分如下情况
3.1如果发现当前的符号栈为空，就直接入栈
3.2如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数,从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈.
4.当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号，并运行.
5.最后在数栈只有一个数字, 就是表达式的结果

分步细节

首先完成计算器中原栈没有的方法

``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;
		}
		return res;
	}

然后完善计算器的逻辑

定义相关变量

String expression = "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 = ' ';
		String keepNum = "";

开始循环扫描表达式

while(true) {
		//依次得到expression 的每一个字符
		ch = expression.substring(index, index+1).charAt(0);
		//判断ch是什么，然后做相应的处理
					
		}
		//让index + 1, 并判断是否扫描到expression最后.
		index++;
		if (index >= expression.length()) {
			break;
		}
}
				

对扫描到的结果进行下一步的处理

if(operStack.isOper(ch)) {//如果是运算符
	//判断当前的符号栈是否为空
	if(!operStack.isEmpty()) {
		//如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中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.push(res);
			//然后将当前的操作符入符号栈
			operStack.push(ch);
		} else {
			//如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
			operStack.push(ch);
		}
	}else {
		//如果为空直接入符号栈..
		operStack.push(ch); // 1 + 3
	}
} else { 
    numStack.push(ch - 48); //? "1+3" '1' => 1
}
				

这时候你会发现一个问题，就是当你的数字是个两位数甚至是更多位数时，运算竟然失败了。

解决方式如下：

进行判断两个数字是否连着，如果连着就将他们合并成一个多位数进行储存。

	//处理多位数
	keepNum += ch;
	//如果ch已经是expression的最后一位，就直接入栈
	if (index == expression.length() - 1) {
		numStack.push(Integer.parseInt(keepNum));
	}else{
		//判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
		//注意是看后一位，不是index++
		if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
			//如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
			numStack.push(Integer.parseInt(keepNum));
			//重要的, keepNum清空
			keepNum = "";
		}
	}