问题描述】
设计一个简单的算术表达式计算器。
【基本要求】
实现标准整数类型的四则运算表达式的求值(包含括号,可多层嵌入).
【测试数据】
( ( 8 + 9 ) * 6 + 2 )
( 7 *( 2 - 7 )+ 10 )* 5
【实现提示】
要求自行设计非法表达式,进行程序测试,以保证程序的稳定运行。
1、问题分析和任务定义、
栈是我们计算机中的一种数据结构,它有着先进后出的数据特性。四则运算表达式实现的方式有多种,我们先用栈的数据结构来实现这个算法,在Java中是没有直接的栈结构的,所以要实现此算法,我们的工作有两步:
用Java常见的数据类型设计stack类,并根据算法实现的需求设计合理的工具方法
理清实现思路用代码表述出来
在这里我们的栈用数据来模拟实现,因为我们是用数组模拟实现的所以我们栈的大小一定是固定的,在我们存取数据的时候应该判断当前栈是否已经满了或是是否里面没有数据以避免数组访问越界,我们对数据的存取需要两个方法。这四个方法可以说是我们栈的基础方法。结合我们算法的实现还需要:判断是否为操作符、操作符优先级的比较、查看栈顶元素、传进操作数操作符的计算。
2、逻辑设计、
import java.util.Scanner;
public class shiyan2{
static Scanner sc=new Scanner(System.in);
public static void main(String[] args) {
//设置表达式
String expression =sc.next();
StackArray numStack = new StackArray(10);
StackArray operStack = new StackArray(10);
//定义需要的相关变量
int index = 0;
int num1 = 0;
int num2 = 0;
int oper = 0;
int res =0;
char ch = ' ';
String keepNum = "";
while(true){
ch = expression.substring(index,index+1).charAt(0);
if (operStack.isOper(ch)){
if(operStack.isEmpty()){
operStack.push(ch);
}else{
if(ch=='('){
operStack.push(ch);
}else if(ch==')'){
while (!(operStack.peek()=='(')){
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
numStack.push(numStack.cal(num1,num2,oper));
}
operStack.pop();
}else {
if(operStack.priority(ch)<=operStack.priority(operStack.peek())){
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
numStack.push(numStack.cal(num1,num2,oper));
operStack.push(ch);
}else{
operStack.push(ch);
}
}
}
}else{
keepNum += ch;
if (index == expression.length()-1){
numStack.push(Integer.parseInt(keepNum));
}else{
if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
numStack.push(Integer.parseInt(keepNum));
keepNum="";
}
}
}
index ++;
if(index==expression.length()){
break;
}
}
while (true){
if(operStack.isEmpty()){
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1,num2,oper);
numStack.push(res);
}
int resUltimately = numStack.pop();
System.out.printf("表达式%s=%d",expression,resUltimately);
}
}
class StackArray {
private int maxCapacity;
private int[] stackArrays;
private int stackTop = -1;
public StackArray (int maxCapacity){
this.maxCapacity = maxCapacity;
this.stackArrays = new int[maxCapacity];
}
public boolean isFull (){
return stackTop == maxCapacity-1;
}
public boolean isEmpty (){
return stackTop==-1;
}
public void push(int element){
if(isFull()){
System.out.println("栈满");
}
stackTop ++;
stackArrays[stackTop] = element;
}
public int pop(){
if (isEmpty()){
throw new RuntimeException("现在栈为空");
}
return stackArrays[stackTop--];
}
public int peek(){
return stackArrays[stackTop];
}
public void list(){
if(isEmpty()){
System.out.println("栈空,没有数据");
}
for (int i = stackTop; i >=0 ; i--) {
System.out.printf("stackArrays[%d]=%dn",i,stackArrays[i]);
}
}
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 == '/'||val=='('||val==')';
}
//计算方法
public int cal(int num1, int num2, int oper) {
int res = 0; // res 用于存放计算的结果
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;
}
}



