/*将中缀表达式--转化为后缀表达式--属于栈的一种应用
*具体思路：
*1.扫描字符串，遇到操作数字符直接不管，存到一个字符串里边
*2.操作符优先级比较--定义了方法
* 栈中优先级高：出栈存进字符串，当前的操作符进栈
* 当前操作符优先级高，直接进栈
* 对于左边括号直接进栈，右边括号涉及栈中出栈
*3.扫描完了在将栈中的出栈和操作数存储在一起
*转化完直观的表现：操作数相对位置不变，操作符相对位置相反
* */
public class IntoSuffixExpression {
private CharStack stack;
private String input;
private String output = ""; public IntoSuffixExpression(String in) {
input = in;
stack = new CharStack(input.length());
} //转化为后缀表达式
public String doTrans(){
for(int i = 0; i < input.length();i++){
char ch = input.charAt(i);
stack.displayStack("For " + ch + " ");
/*分析读到的元素的类型--操作符/操作数(默认添加到输出字符串中)
*对于操作符分类并进行优先级比较 乘除优先级高于加减*/
switch(ch){
case '+':
case '-':
gotOper(ch,1);//需要判断优先级prec1：设定的是当前的优先级
break;
case '*':
case '/':
gotOper(ch,2);//需要判断优先级
break;
case '(':
stack.push(ch);//左括号优先级最高直接进栈
break;
case ')':
gotParent(ch);//碰到右边括号涉及出栈
break;
default:
output = output + ch;//是操作数就直接存在输出字符串中
break;
}
}
//打印战中的操作符返回后缀表达式字符串
while(!stack.isEmpty()){
stack.displayStack("while");
output = output + stack.pop();
}
stack.displayStack("end");
return output;
} //比较当前的操作符与栈里面的操作符优先级--进行不同的操作
public void gotOper(char opThis, int prec1) {
while(!stack.isEmpty()){
char opTop = stack.pop();
if(opTop == '('){ //如果栈中顶是左边括号就进去跳出循环
stack.push(opTop);
break;
}
else{
int prec2;
//记录栈中操作符优先级--加减优先级是1乘除优先级是2
if(opTop == '+' || opTop == '-'){
prec2 = 1;
}
else{
prec2 = 2;
}
//栈中优先级小结束比较--当前执行进栈操作
if(prec2 < prec1){
stack.push(opTop);
break;
}
//栈中优先级大就出栈存储在字符串中
else{
output = output + opTop;
}
}
}
//栈为空就直接进栈或者遇到左边括号也是直接进栈或者栈存储比栈中优先级小的
stack.push(opThis);
} //越到右边括号进行出栈的操作--直到遇到左边括号
public void gotParent(char ch){
while(!stack.isEmpty()){
char chx = stack.pop();
if(chx == '('){
break;
}
else{
output = output + chx;
}
}
} }
/*计算后缀表达式的值--也用的是栈
* */
public class CalculateSuffixExpression {
private MyStack stack;
private String input; //注意这里传入的字符串是后缀的表达式
public CalculateSuffixExpression(String in) {
input = in;
} //数字进栈，操作符栈中元素出栈对应相应的操作
public long calculateValue(){
stack = new MyStack(20);
char ch;
int j;
long num1,num2,interAns;
for(j = 0;j < input.length();j++){
ch = input.charAt(j);
stack.displayStack("" + ch + "");
if(ch >= '0' && ch <= '9'){ //操作数
stack.push((long)(ch - '0'));
}
else{
num2 = stack.pop();
num1 = stack.pop();
switch(ch){
case'+':
interAns = num1 + num2;
break;
case'-':
interAns = num1 - num2;
break;
case'*':
interAns = num1 * num2;
break;
case'/':
interAns = num1 / num2;
break;
default:
interAns = 0;
}
stack.push(interAns);
}//end else
}//end for
interAns = stack.pop();
return interAns;
}//end method public static void main(String[] args){
//转化后缀表达式
String s = "3+(6*9)+2-6/(3-1)";
IntoSuffixExpression is = new IntoSuffixExpression(s);
String out = is.doTrans(); //计算后缀表达式
CalculateSuffixExpression cse = new CalculateSuffixExpression(out);
long result = cse.calculateValue();
System.out.println(result); } }