用栈结构解析四则运算
对于四则运算大家都不陌生了吧!
相信能看懂这篇文章上字的人基本都会算四则运算。但是怎么让计算机去解析这个四则运算呢?
计算机只能计算+ - * / % 如果四则运算的表达式中出现括号,那又该怎么办呢?这里呢,就需要用到一定的数学知识了!我们书写的四则运算表达式一般是用中缀式(eg:5*(2+3*(6-3)/5)+7),这样的字符串给计算机运算带来很大的困难,那么我这里引入后缀表达式如下:
这样太抽象了,来举几个例子给大家看看中缀表达式是怎么转换成后缀式子的
那我们怎么把中缀表达式转换成后缀表达式呢?看如下示例~~
我们用代码来看看怎么转换
private void calculator(String operation) {
char[] opr = operation.toCharArray(); // 将字符串转换成字符数组
// 先在符号栈中加入'#',方便判断pop的时候是否取完符号
optr.push('#');
// 逐个字符解析
for (int i = 0; i < opr.length; i++) {
char temp = opr[i];
// 如果是数字压入后缀式栈中
if ((int) temp >= 48 && (int) temp <= 57) {
pofix.push(temp);
}
// 如果读到'#',表示表达式已经历遍完了
else if (temp == '#') {
// 把剩下的运算符压入后缀表达式栈中
while (true) {
char left = (char) optr.pop();
// 如果在运算符栈中读到'#',那么表示所有运算符已经读完
if (left == '#') {
break;
} else {
pofix.push(left);
}
}
}
// 如果是运算符(包括括号)
else {
// 如果是左括号,压入运算符栈中
if (temp == '(') {
optr.push('(');
}
// 如果是右括号,运算符出栈直到匹配到左括号
else if (temp == ')') {
System.out.println("匹配到右括号");
while (true) {
char getTop = (char) optr.pop();
// 如果是左括号,则一次匹配结束
if (getTop == '(')
break;
// 如果不是左括号,出运算符栈,压入后缀表达式栈
System.out.println("getTop = " + getTop);
pofix.push(getTop);
}
}
// 如果不是括号,和栈顶元素比较优先级,再确定是否入栈
else {
// 获取栈顶元素
char topTemp = (char) optr.pop();
// 如果取得运算符优先级比栈顶的高,直接压入运算符栈
if (priority(temp) >priority(topTemp)) {
System.out.println("topTemp = " + topTemp + " temp = "
+ temp);
optr.push(topTemp);
optr.push(temp);
} else {
// 如果低的话,就把栈顶运算符压入后缀式栈中,把取得运算符压入运算符栈中
optr.push(temp);
pofix.push(topTemp);
}
}
}
}
/**
* 操作符优先级方法
*
* @param ch
* @return 优先级
*/
private int priority(char ch) {
switch (ch) {
case '#':
return 0;
case '(':
return 1;
case '+':
return 3;
case '-':
return 3;
case '*':
return 5;
case '/':
return 5;
case ')':
return 7;
default:
JOptionPane.showMessageDialog(null, "输入表达式中存在不合法字符");
return -1;// 因为不可能不匹配,除非表达式中存在不合法字符
}
}
这样我们就已经实现了把中缀表达式转换成后缀表达式了!
有了后缀表达式,我们怎么去是实现计算呢?例如这个后缀表达式(12345+-*+),由于以上代码把后缀表达式放在了一个栈结构中,而且自顶向下是(+*-+54321),这样显然不好操作。我们给自定义栈中加了一个方法,把栈倒置。
package cn.jinyejun.experiment_Stack;
/**
* 用数组实现栈结构
*
* @author 金晔俊 日期:2014.4.4
* @param <E>
*/
public class MyStack<E> {
private Object stack[];
private final static int UPDATE_SIZE = 5; // 栈空间更新大小
private int top = 0; // 初始化栈顶
private int size = 0; // 初始化栈大小
/**
* 构造方法,初始化一个大小为0的栈
*/
public MyStack() {
this(0);
}
/**
* 构造方法,初始化一个大小为size的栈
*
* @param size
*/
public MyStack(int size) {
stack = new Object[size];
this.size = size;
}
/**
* 入栈
* @param e
*/
public void push(E e) {
// 如果栈满,增加栈大小
if (isFull()) {
Object newStack[] = new Object[stack.length + UPDATE_SIZE];
for(int i=0;i<stack.length;i++){
newStack[i]=stack[i];
}
stack = newStack;
size = size + UPDATE_SIZE; // 更新栈大小
}
stack[top++] = e;
}
/**
* 出栈
* @return stack[top--];
*/
public Object pop(){
//如果栈空,抛出异常
if(isEmpty()){
throw new java.lang.IndexOutOfBoundsException("栈空!");
}else{
Object topElement = stack[--top];
stack[top] = null; //清空栈顶
size--;
return topElement;
}
}
public int getSize(){
return size;
}
/**
* 判断是否栈满
* @return top >= size
*/
public boolean isFull() {
return top >= size;
}
/**
* 判断是否空栈
* @return top == 0
*/
public boolean isEmpty() {
return top == 0;
}
/**
* 倒置栈
*
*/
public void changeOrder(){
System.out.println("top-->?"+top);
Object[] newStack = new Object[stack.length];
for(int i = top-1;i>=0;i--){
newStack[top-1-i] = stack[i];
}
stack = newStack;
System.out.println("转换后的栈————————");
for(int i = 0;i<top;i++){
System.out.println("change"+stack[i]);
}
}
}
这样后缀表达式在栈中自顶向下就是这么存放了(12345+-*+),有了这个东西,我们可以自顶向下的方式去遍历这个栈,如果是数字就把数字放到一个新的栈结构(这里我们把它叫做计算栈)中,如果是运算符,就在运算栈里依次取出两个数字b,a进行相应计算(比如运算符是-,那么就是a-b),然后把计算得到的结构再放入计算栈中,直到遍历完后缀表达式存放的那个栈为止,然后取出计算栈中的数字就是表达式计算结果!
代码如下:
// 先把后缀表达式栈倒序
pofix.changeOrder();
// 遍历新的后缀表达式栈
while (!pofix.isEmpty()) {
char tempOpr = (char) pofix.pop();
// 如果是数字送入计算栈
if (tempOpr>= '0' &&tempOpr<= '9'){
calStack.push((int)(tempOpr-48));
}else{
//如果不是取计算栈中的栈顶元素进行符号计算
int b = (int) calStack.pop();
int a = (int) calStack.pop();
int c;
switch(tempOpr){
case '+':
c = a+b;
System.out.println("计算结果+ "+c);
calStack.push(c);
break;
case '-':
c = a-b;
System.out.println("计算结果- "+c);
calStack.push(c);
break;
case '*':
c = a*b;
System.out.println("计算结果* "+c);
calStack.push(c);
break;
case '/':
c = a/b;
System.out.println("计算结果/ "+c);
calStack.push(c);
break;
}
}
}
int result = (int) calStack.pop();
System.out.println(result);
}
完整版代码(包含了图形界面哦,以及在代码编写过程中的调试syso哦)
自定义栈类:
package cn.jinyejun.experiment_Stack;
/**
* 用数组实现栈结构
*
* @author 金晔俊 日期:2014.4.4
* @param <E>
*/
public class MyStack<E> {
private Object stack[];
private final static int UPDATE_SIZE = 5; // 栈空间更新大小
private int top = 0; // 初始化栈顶
private int size = 0; // 初始化栈大小
/**
* 构造方法,初始化一个大小为0的栈
*/
public MyStack() {
this(0);
}
/**
* 构造方法,初始化一个大小为size的栈
*
* @param size
*/
public MyStack(int size) {
stack = new Object[size];
this.size = size;
}
/**
* 入栈
* @param e
*/
public void push(E e) {
// 如果栈满,增加栈大小
if (isFull()) {
Object newStack[] = new Object[stack.length + UPDATE_SIZE];
for(int i=0;i<stack.length;i++){
newStack[i]=stack[i];
}
stack = newStack;
size = size + UPDATE_SIZE; // 更新栈大小
}
stack[top++] = e;
}
/**
* 出栈
* @return stack[top--];
*/
public Object pop(){
//如果栈空,抛出异常
if(isEmpty()){
throw new java.lang.IndexOutOfBoundsException("栈空!");
}else{
Object topElement = stack[--top];
stack[top] = null; //清空栈顶
size--;
return topElement;
}
}
public int getSize(){
return size;
}
/**
* 判断是否栈满
* @return top >= size
*/
public boolean isFull() {
return top >= size;
}
/**
* 判断是否空栈
* @return top == 0
*/
public boolean isEmpty() {
return top == 0;
}
public void changeOrder(){
System.out.println("top-->?"+top);
Object[] newStack = new Object[stack.length];
for(int i = top-1;i>=0;i--){
newStack[top-1-i] = stack[i];
}
stack = newStack;
System.out.println("转换后的栈————————");
for(int i = 0;i<top;i++){
System.out.println("change"+stack[i]);
}
}
}
四则运算类:
package cn.jinyejun.experiment_Stack;
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JTextField;
public class AnalyzeOperate extends JFrame {
private MyStack<Character> optr = new MyStack<Character>(); // 操作符栈
private MyStack<Character> pofix = new MyStack<Character>(); // 后缀表达式栈
private MyStack<Integer> calStack = new MyStack<Integer>(); // 用于取后缀表达式栈中的元素计算栈
private JLabel jlb;
private JLabel jlbr;
private JLabel jlbp;
private JTextField jtf;
private JButton jbu;
private String operation; // 存放表达式
public AnalyzeOperate() {
initUI();
}
// 初始化界面
private void initUI() {
this.setTitle("用栈结构实现四则运算");
this.setLayout(new FlowLayout());
this.setSize(300, 150);
this.setResizable(false);
this.setLocationRelativeTo(null);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
// 提示标签
jlb = new JLabel("请输入四则运算表达式");
jlbr = new JLabel("计算结果:");
jlbp = new JLabel("____");
// 实例化四则运算输入框和计算按钮
jtf = new JTextField(25);
jbu = new JButton("calculator");
this.add(jlb);
this.add(jtf);
this.add(jbu);
this.add(jlbr);
this.add(jlbp);
this.setVisible(true);
jbu.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
operation = jtf.getText(); // 获取表达式字符串
calculator(operation + "#");// 解析表达式
}
});
}
/**
* 解析表达式进行运算
*
* @param operation
*/
private void calculator(String operation) {
char[] opr = operation.toCharArray(); // 将字符串转换成字符数组
// 先在符号栈中加入'#',方便判断pop的时候是否取完符号
optr.push('#');
// 逐个字符解析
for (int i = 0; i < opr.length; i++) {
char temp = opr[i];
// 如果是数字压入后缀式栈中
if ((int) temp >= 48 && (int) temp <= 57) {
pofix.push(temp);
}
// 如果读到'#',表示表达式已经历遍完了
else if (temp == '#') {
// 把剩下的运算符压入后缀表达式栈中
while (true) {
char left = (char) optr.pop();
// 如果在运算符栈中读到'#',那么表示所有运算符已经读完
if (left == '#') {
break;
} else {
pofix.push(left);
}
}
}
// 如果是运算符(包括括号)
else {
// 如果是左括号,压入运算符栈中
if (temp == '(') {
optr.push('(');
}
// 如果是右括号,运算符出栈直到匹配到左括号
else if (temp == ')') {
System.out.println("匹配到右括号");
while (true) {
char getTop = (char) optr.pop();
// 如果是左括号,则一次匹配结束
if (getTop == '(')
break;
// 如果不是左括号,出运算符栈,压入后缀表达式栈
System.out.println("getTop = " + getTop);
pofix.push(getTop);
}
}
// 如果不是括号,和栈顶元素比较优先级,再确定是否入栈
else {
// 获取栈顶元素
char topTemp = (char) optr.pop();
// 如果取得运算符优先级比栈顶的高,直接压入运算符栈
if (priority(temp) >priority(topTemp)) {
System.out.println("topTemp = " + topTemp + " temp = "
+ temp);
optr.push(topTemp);
optr.push(temp);
} else {
// 如果低的话,就把栈顶运算符压入后缀式栈中,把取得运算符压入运算符栈中
optr.push(temp);
pofix.push(topTemp);
}
}
}
}
//转换前
// System.out.println("转换前的栈-------");
// while (!pofix.isEmpty()) {
// System.out.println(pofix.pop());
// }
// 先把后缀表达式栈倒序
pofix.changeOrder();
// while (!pofix.isEmpty()) {
// System.out.println(pofix.pop());
// }
// 遍历新的后缀表达式栈
while (!pofix.isEmpty()) {
char tempOpr = (char) pofix.pop();
// 如果是数字送入计算栈
if (tempOpr>= '0' &&tempOpr<= '9'){
calStack.push((int)(tempOpr-48));
}else{
//如果不是取计算栈中的栈顶元素进行符号计算
int b = (int) calStack.pop();
int a = (int) calStack.pop();
int c;
switch(tempOpr){
case '+':
c = a+b;
System.out.println("计算结果+ "+c);
calStack.push(c);
break;
case '-':
c = a-b;
System.out.println("计算结果- "+c);
calStack.push(c);
break;
case '*':
c = a*b;
System.out.println("计算结果* "+c);
calStack.push(c);
break;
case '/':
c = a/b;
System.out.println("计算结果/ "+c);
calStack.push(c);
break;
}
}
}
int result = (int) calStack.pop();
System.out.println(result);
jlbp.setText(""+result);
this.repaint();
}
/**
* 操作符优先级方法
*
* @param ch
* @return 优先级
*/
private int priority(char ch) {
switch (ch) {
case '#':
return 0;
case '(':
return 1;
case '+':
return 3;
case '-':
return 3;
case '*':
return 5;
case '/':
return 5;
case ')':
return 7;
default:
JOptionPane.showMessageDialog(null, "输入表达式中存在不合法字符");
return -1;// 因为不可能不匹配,除非表达式中存在不合法字符
}
}
public static void main(String[] args) {
new AnalyzeOperate();
}
}