栈实现综合计算器的代码以及中缀表达式转换为后缀表达式的步骤
【摘要】 栈实现综合计算器定义ArrayStack2类,表示栈class ArrayStack2 { private int maxSize;//栈的大小 private int[] stack;//用数组模拟栈,将数据放到数组中 private int top = -1;//表示栈顶,默认值为 -1 public ArrayStack2(int maxSize) { ...
栈实现综合计算器
定义ArrayStack2类,表示栈
class ArrayStack2 {
private int maxSize;//栈的大小
private int[] stack;//用数组模拟栈,将数据放到数组中
private int top = -1;//表示栈顶,默认值为 -1
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
//栈满
public boolean isFull() {
return top == maxSize - 1;
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//入栈-push
public void push(int value) {
//先判断栈是否为满
if(isFull()) {
System.out.println("栈满");
return;
}
stack[++top] = value;
}
//出栈-pop,将栈顶的数据返回
public int pop() {
//先判断栈是否为空
if(isEmpty()) {
// System.out.println("栈空");
// return;
// 因为有返回值,所以不能用这种返回的方式
throw new RuntimeException("栈空");
}
int value = stack[top--];
return value;
}
//显示栈的情况(遍历栈),遍历时,需要从栈顶开始显示数据
public void list() {
//判断栈是否为空
if(isEmpty()) {
System.out.println("栈空");
return;
}
//从栈顶开始显示数据
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d] = %d\n",i,stack[i]);
}
}
//判断字符是否为加减乘除
public boolean isOperator(char val) {
return val == '+' || val == '-' || val == '*' || val == '/';
}
//返回运算符的优先级,优先级的表示是自定的,这里我们使用数字表示
public int priority(int operator) {
if(operator == '*' || operator == '/') {
return 1;
} else if(operator == '+' || operator == '-') {
return 0;
} else {
return -1;
}
}
//计算方法
public int calculation(int num1 , int num2 , int operator) {
int result = 0;
switch (operator) {
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1;//注意顺序
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1;
break;
default:
break;
}
return result;
}
//增加一个方法,用来查看当前栈顶的值,但不是真正的pop
public int peek() {
return stack[top];
}
}
定义Calculator类进行演示
import java.util.Scanner;
public class Calculator {
public static void main(String[] args) {
//输入表达式
Scanner scanner = new Scanner(System.in);
String expression = scanner.next();
//创建两个栈,分别存放数据和符号
ArrayStack2 numberStack = new ArrayStack2(10);
ArrayStack2 operatorStack = new ArrayStack2(10);
//定义相关变量
int num1 = 0;
int num2 = 0;
int index = 0;//用于扫描
int result = 0;
int operator = 0;
char ch = ' ';//每次扫描得到的字符存放到ch中
//开始while循环扫描expression
while(true) {
//依次得到expression的每一个字符
ch = expression.substring(index , index + 1).charAt(0);//截取
//判断ch是数字还是符号,并做出响应操作
if(operatorStack.isOperator(ch)) {
//先判断符号栈是否为空,然后进行操作
if(operatorStack.isEmpty()){
//如果此栈为空,就直接入符号栈
operatorStack.push(ch);
} else {
//如果此栈不为空,其中含有操作符,则要进行比较
/*
如果当前的操作符的优先级小于或者等于栈顶的操作符,
就需要从数栈中pop出两个数据,再从符号栈中pop出一个符号,
进行计算,得到结果,入数栈,然后将当前的操作符入符号栈
*/
if(operatorStack.priority(ch) <= operatorStack.priority(operatorStack.peek())) {
num1 = operatorStack.pop();
num2 = operatorStack.pop();
operator = operatorStack.pop();
result = operatorStack.calculation(num1 , num2 , operator);
//将运算后的结果入栈
numberStack.push(result);
//将当前的操作符入符号栈
operatorStack.push(ch);
} else {
//如果当前的操作符的优先级大于栈中的操作符,就直接入栈
operatorStack.push(ch);
}
}
} else {
//如果是数,则直接入数栈
numberStack.push(ch - 48);//因为ch此时是字符型
}
//让index + 1,并判断是否扫描到expression最后
index++;
if(index >= expression.length()) {
break;
}
}
//当表达式扫描完毕后,就按顺序从数栈中pop出相应的数字和字符,进行运算
while(true) {
//如果符号栈为空,则代表计算到了最后的一个结果,数字栈中的栈顶就是结果
if(operatorStack.isEmpty()) {
break;
}
num1 = numberStack.pop();
num2 = numberStack.pop();
operator = operatorStack.pop();
result = numberStack.calculation(num1 , num2 , operator);
numberStack.push(result);//将计算结果入栈
}
System.out.printf("表达式%s = %d" , expression , numberStack.pop());
}
}
中缀表达式转后缀表达式
具体步骤:
(1)初始化两个栈,运算符栈s1和存储中间结果的栈s2
(2)从左至右扫描中缀表达式
(3)遇到操作数时,将其压s2
(4)遇到运算符时,比较其s1栈顶运算符的优先级
1)如果s1为空,或栈顶运算符为左括号,则直接将此运算符入栈;
2)否则,若优先级比栈顶运算符高,也将运算符压入s1
3)否则,将s1的栈顶d额运算符弹出并压入s2中,再次转到(4-1)与s1中新的栈顶运算符相比较
(5)遇到括号时
1)如果是左括号,则直接压入s1
2)如果是右括号,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
(6)重复步骤2和5,直到表达式的最右边
(7)将s1中剩余的运算符依次弹出并压入s2
(8)依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)