数据结构之中缀表达式转为后缀表达式

totty

浏览: 23811 次
性别:
来自: 北京

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (13)

社区版块

存档分类

数据结构

将中缀表达式转为后缀表达式后，利用计算机计算表达式更容易。

ExpressionCal.java 代码

public class ExpressionCal {
// 构建一个栈
class Stack {
private int top;
private char[] stackArray;
// 栈构造函数
public Stack(int s) {
stackArray = new char[s];
top = -1;
}
// 入栈
public void push(char i) {
stackArray[++top] = i;
}
// 出栈
public char pop() {
return stackArray[top--];
}
public int size() {
return top + 1;
}
public boolean isEmpty() {
return (top == -1);
}
public void displayStack(String s) {
System.out.print(s);
for (int i = 0; i < size(); i++) {
System.out.print(stackArray[i]);
System.out.print(' ');
}
System.out.println(" ");
}
}
// 将中缀表达式转换为后缀表达式类
class PostExpression {
private Stack postExpStack;
private String input;
private String output = "";
public PostExpression(String expression) {
input = expression;
postExpStack = new Stack(expression.length());
}
// 将中缀表达式变成后缀表达式
public String transPostExp() {
for (int i = 0; i < input.length(); i++) {
postExpStack.displayStack("no" + i + " stack is: ");
char ch = input.charAt(i);
switch (ch) {
case '+':
case '-':
doOper1(ch, 1);
break;
case '*':
case '/':
doOper1(ch, 2);
break;
case '(':
postExpStack.push(ch);
break;
case ')':
doOper2();
break;
default:
output += ch;
break;
}
System.out.println("no" + i + " output: " + output);
}
while (!postExpStack.isEmpty()) {
output += postExpStack.pop();
}
postExpStack.displayStack("final stack is: ");
return output;
}
// 根据读取的字符是+-*/的时候做处理
private void doOper1(char ch, int num) {
while (!postExpStack.isEmpty()) {
char chPop = postExpStack.pop();
if (chPop == '(') {
postExpStack.push(chPop);
break;
} else {
int opernum;
if (chPop == '+' || (chPop == '-')) {
opernum = 1;
} else
opernum = 2;
if (num > opernum) {
postExpStack.push(chPop); // 读取的操作符为*/，而栈顶内容为+-，则将*/入栈
break;
} else {
output += chPop;
}
}
}
postExpStack.push(ch);
}
// 读取的字符为)时的处理方式
private void doOper2() {
while (!postExpStack.isEmpty()) {
char chPop = postExpStack.pop();
if (chPop == '(') {
break;
} else {
output += chPop;
}
}
}
}
public static void main(String[] args) {
PostExpression pe = new ExpressionCal().new PostExpression(
"(1+(4-6/2))*3");
System.out.println("after trans: " + pe.transPostExp());
}
}

运行结果如下：

no0 stack is:
no0 output:
no1 stack is: (
no1 output: 1
no2 stack is: (
no2 output: 1
no3 stack is: ( +
no3 output: 1
no4 stack is: ( + (
no4 output: 14
no5 stack is: ( + (
no5 output: 14
no6 stack is: ( + ( -
no6 output: 146
no7 stack is: ( + ( -
no7 output: 146
no8 stack is: ( + ( - /
no8 output: 1462
no9 stack is: ( + ( - /
no9 output: 1462/-
no10 stack is: ( +
no10 output: 1462/-+
no11 stack is:
no11 output: 1462/-+
no12 stack is: *
no12 output: 1462/-+3
final stack is:
after trans: 1462/-+3*

利用最后的结果1462/-+3*就比较容易用栈实现计算了，按顺序读数，数字入栈，当读到操作符后用栈顶两个数做计算，并将结果入栈，所以是1462先入栈，读到/，62出栈做6/2=3，3入栈，读到-，再43出栈做4-3=1，再1入栈，读到+，再11出栈做1+1=2，2入栈，再3入栈，读到*，23出栈做2*3=6为最后结果。

分享到：