Go语言视频零基础入门到精通

javalearner · 发表于 2014-10-30 23:59:45

栈的应用实例
一、中缀表达式转换为后缀表达式（只处理了+,-,*,/,(,))的代码：

// infix.java
// converts infix arithmetic expressions to postfix
// to run this program: C>java InfixApp
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize;
private char[] stackArray;
private int top;
//--------------------------------------------------------------
public StackX(int s) // constructor
{
maxSize = s;
stackArray = new char[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(char j) // put item on top of stack
{ stackArray[++top] = j; }
//--------------------------------------------------------------
public char pop() // take item from top of stack
{ return stackArray[top--]; }
//--------------------------------------------------------------
public char peek() // peek at top of stack
{ return stackArray[top]; }
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{ return (top == -1); }
//-------------------------------------------------------------
public int size() // return size
{ return top+1; }
//--------------------------------------------------------------
public char peekN(int n) // return item at index n
{ return stackArray[n]; }
//--------------------------------------------------------------
public void displayStack(String s)
{
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for(int j=0; j< size(); j++)
{
System.out.print( peekN(j) );
System.out.print(" ");
}
System.out.println("");
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class InToPost // infix to postfix conversion
{
private StackX theStack;
private String input;
private String output = "";
//--------------------------------------------------------------
public InToPost(String in) // constructor
{
input = in;
int stackSize = input.length();
theStack = new StackX(stackSize);
}
//--------------------------------------------------------------
public String doTrans() // do translation to postfix
{
for(int j=0; j< input.length(); j++) // for each char
{
char ch = input.charAt(j); // get it
theStack.displayStack("For "+ch+" "); // *diagnostic*
switch(ch)
{
case "+": // it"s + or -
case "-":
gotOper(ch, 1); // go pop operators
break; // (precedence 1)
case "*": // it"s * or /
case "/":
gotOper(ch, 2); // go pop operators
break; // (precedence 2)
case "(": // it"s a left paren
theStack.push(ch); // push it
break;
case ")": // it"s a right paren
gotParen(ch); // go pop operators
break;
default: // must be an operand
output = output + ch; // write it to output
break;
} // end switch
} // end for
while( !theStack.isEmpty() ) // pop remaining opers
{
theStack.displayStack("While "); // *diagnostic*
output = output + theStack.pop(); // write to output
}
theStack.displayStack("End "); // *diagnostic*
return output; // return postfix
} // end doTrans()
//--------------------------------------------------------------
public void gotOper(char opThis, int prec1)
{ // got operator from input
while( !theStack.isEmpty() )
{
char opTop = theStack.pop();
if( opTop == "(" ) // if it"s a "("
{
theStack.push(opTop); // restore "("
break;
}
else // it"s an operator
{
int prec2; // precedence of new op
if(opTop=="+" || opTop=="-") // find new op prec
prec2 = 1;
else
prec2 = 2;
if(prec2 < prec1) // if prec of new op less
{ // than prec of old
theStack.push(opTop); // save newly-popped op
break;
}
else // prec of new not less
output = output + opTop; // than prec of old
} // end else (it"s an operator)
} // end while
theStack.push(opThis); // push new operator
} // end gotOp()
//--------------------------------------------------------------
public void gotParen(char ch)
{ // got right paren from input
while( !theStack.isEmpty() )
{
char chx = theStack.pop();
if( chx == "(" ) // if popped "("
break; // we"re done
else // if popped operator
output = output + chx; // output it
} // end while
} // end popOps()
//--------------------------------------------------------------
} // end class InToPost
////////////////////////////////////////////////////////////////
class InfixApp
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
System.out.print("Enter infix: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // quit if [Enter]
break;
// make a translator
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans(); // do the translation
System.out.println("Postfix is " + output + "
");
} // end while
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
} // end class InfixApp
////////////////////////////////////////////////////////////////

复制代码

  运行结果：
C:xx>java InfixApp
Enter infix: a+b*(c-d)
For a Stack (bottom-->top):
For + Stack (bottom-->top):
For b Stack (bottom-->top): +
For * Stack (bottom-->top): +
For ( Stack (bottom-->top): + *
For c Stack (bottom-->top): + * (
For - Stack (bottom-->top): + * (
For d Stack (bottom-->top): + * ( -
For ) Stack (bottom-->top): + * ( -
While Stack (bottom-->top): + *
While Stack (bottom-->top): +
End Stack (bottom-->top):
Postfix is abcd-*+












  二、求后缀表达式的值（只处理了一位数）

// postfix.java
// parses postfix arithmetic expressions
// to run this program: C>java PostfixApp
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize;
private int[] stackArray;
private int top;
//--------------------------------------------------------------
public StackX(int size) // constructor
{
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(int j) // put item on top of stack
{ stackArray[++top] = j; }
//--------------------------------------------------------------
public int pop() // take item from top of stack
{ return stackArray[top--]; }
//--------------------------------------------------------------
public int peek() // peek at top of stack
{ return stackArray[top]; }
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{ return (top == -1); }
//--------------------------------------------------------------
public boolean isFull() // true if stack is full
{ return (top == maxSize-1); }
//--------------------------------------------------------------
public int size() // return size
{ return top+1; }
//--------------------------------------------------------------
public int peekN(int n) // peek at index n
{ return stackArray[n]; }
//--------------------------------------------------------------
public void displayStack(String s)
{
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for(int j=0; j< size(); j++)
{
System.out.print( peekN(j) );
System.out.print(" ");
}
System.out.println("");
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class ParsePost
{
private StackX theStack;
private String input;
//--------------------------------------------------------------
public ParsePost(String s)
{ input = s; }
//--------------------------------------------------------------
public int doParse()
{
theStack = new StackX(20); // make new stack
char ch;
int j;
int num1, num2, interAns;
for(j=0; j< input.length(); j++) // for each char,
{
ch = input.charAt(j); // read from input
theStack.displayStack(""+ch+" "); // *diagnostic*
if(ch >= "0" && ch <= "9") // if it"s a number
theStack.push( (int)(ch-"0") ); // push it
else // it"s an operator
{
num2 = theStack.pop(); // pop operands
num1 = theStack.pop();
switch(ch) // do arithmetic
{
case "+":
interAns = num1 + num2;
break;
case "-":
interAns = num1 - num2;
break;
case "*":
interAns = num1 * num2;
break;
case "/":
interAns = num1 / num2;
break;
default:
interAns = 0;
} // end switch
theStack.push(interAns); // push result
} // end else
} // end for
interAns = theStack.pop(); // get answer
return interAns;
} // end doParse()
} // end class ParsePost
////////////////////////////////////////////////////////////////
class PostfixApp
{
public static void main(String[] args) throws IOException
{
String input;
int output;
while(true)
{
System.out.print("Enter postfix: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // quit if [Enter]
break;
// make a parser
ParsePost aParser = new ParsePost(input);
output = aParser.doParse(); // do the evaluation
System.out.println("Evaluates to " + output);
} // end while
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
} // end class PostfixApp
////////////////////////////////////////////////////////////////
运行结果：
C:cs>java PostfixApp
Enter postfix: 345+-
3 Stack (bottom-->top):
4 Stack (bottom-->top): 3
5 Stack (bottom-->top): 3 4
+ Stack (bottom-->top): 3 4 5
- Stack (bottom-->top): 3 9
Evaluates to -6

复制代码

注：3-（4+5）=-6

源码下载：http://file.javaxxz.com/2014/10/30/235945687.zip

		自动登录	找回密码
密码			立即注册

JAVA高级面试进阶视频教程	Java架构师系统进阶VIP课程	分布式高可用全栈开发微服务教程	Go语言视频零基础入门到精通	Java架构师3期(课件+源码)
Java开发全终端实战租房项目视频教程	SpringBoot2.X入门到高级使用教程	大数据培训第六期全套视频教程	深度学习（CNN RNN GAN）算法原理	Java亿级流量电商系统视频教程
互联网架构师视频教程	年薪50万Spark2.0从入门到精通	年薪50万！人工智能学习路线教程	年薪50万！大数据从入门到精通学习路线	年薪50万！机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程	深度学习数据分析基础到实战	最新黑马javaEE2.1就业课程	从 0到JVM实战高手教程	MySQL入门到精通教程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

Java亿级流量电商系统视频教程

年薪50万Spark2.0从入门到精通

年薪50万！人工智能学习路线教程

[算法学习]栈的应用实例:中缀表达式转为后缀表达式

相关帖子