1. 栈的定义
2. 栈的实现
2.1. C++ STL中的Stack
参见：http://www.jb51.cc/article/p-pwuxcimt-yt.html
2.2. Java中的Stack
参见：http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
3. 栈的应用
3.1. 表达式求值
中缀表达式：运算符位于两个操作数之间的表达式；如，1+2×3，中缀表达式的运算一般遵循“先乘除，后加减，从左到右计算，先括号内，后括号外”的规则；中缀表达式不仅要依赖运算符优先级，而且还有处理括号；
后缀表达式：运算符在操作数的后面，如，1+2×3的后缀表达式为123×+；在后缀表达式中已经考虑了运算符的优先级，没有括号，只有操作数和运算符；
后缀表达式求值过程：从左到右读入后缀表达式，如读入的是一个操作数，就将它如数值栈；若读入的是一个运算符op,就从数值栈中连续出栈两个元素，假设为x和y，计算x op y的值，并将计算结果如数值栈。对整个后缀表达式读入结束时，栈顶元素就是计算结果；
表达式求值过程：先将算术表示转换成后缀表达式，然后对该后缀表达式求值；
中缀表达式转后缀表达式过程：设后缀表达式存放在一个数组exp中，操作符栈op；
对于表达式中的每个字符ch:
(1) 若ch为数字，将后续的所有数字依次存入数组exp中；
(2) 若ch为“(”，则将此括弧如栈op；
(3) 若ch为")"，则将栈op中左括弧"("之前(栈顶到"("之间)的字符依次删除并存入数组exp中，然后将左括弧"("删除；
(4) 若ch为“+”或“-”，则将当前栈op中"("之前的所有运算符一次删除并存入数组exp中，然后将ch如栈op中；
(5) 若ch为"*"或"/"，则将当前栈op中栈顶端连续的"*"或"/"删除，并以此存入数组exp中，然后将ch如栈op中；
(6) 若表达式字符串扫描完毕，则将栈op中的所有运算符一次删除并存入数组exp中，最后得到的表达式的后缀表示在数组exp中。
import java.util.*;
import java.util.Stack;
import java.util.Vector;
import java.io.*;
/**
* Test
*/
public class Calculator
{
public static void main(String[] args)
{
String expStr = new String ("(56 - 20) / (4 + 2)");
Expression exp = new Expression(expStr);
exp.translateToPostfixExp();
System.out.println(exp.getPostfixExpStringValue());
System.out.println("The result is: " + exp.calculate());
}
}
/**
* super class for operator and number
*/
interface BulkObject
{
public String getStringValue();
}
/**
* number object
*/
class NumberObject implements BulkObject
{
private double number = 0.0;
public NumberObject(double num)
{
this.number = num;
}
public String getStringValue()
{
return String.valueOf(number);
}
public double getValue()
{
return number;
}
}
/**
* operator object
*/
class OperatorObject implements BulkObject
{
private String operator = new String();
public OperatorObject(String op)
{
this.operator = op;
}
public String getStringValue()
{
return operator;
}
public String getValue()
{
return operator;
}
}
/**
* expression object
*/
class Expression
{
// string of expression
public String expStr = new String();
// array of number and operator for post fix expression
public Vector<BulkObject> postfixExp = new Vector<BulkObject>();
/**
* constructor
*/
public Expression(String expStr)
{
this.expStr = expStr;
}
/**
* return the string value of the post fix expression
*/
public String getPostfixExpStringValue()
{
String strValue = new String();
for (BulkObject ele : postfixExp)
{
strValue += ele.getStringValue() + " ";
}
return strValue;
}
/**
* translate the expression to post fix format
*/
public void translateToPostfixExp()
{
// operator stack
Stack<OperatorObject> opStack = new Stack<OperatorObject>();
int length = expStr.length();
// for each char in the expression string
for (int i = 0; i < length; i++)
{
char ch = expStr.charAt(i);
switch (ch)
{
// ignore the space
case ' ':
{
}
break;
// push stack
case '(':
{
opStack.push(new OperatorObject(Character.toString(ch)));
}
break;
// pop all the operators before the '('
case ')':
{
while (!opStack.empty())
{
OperatorObject op = opStack.pop();
if (op.getValue().equals("("))
{
break;
}else
{
postfixExp.add(op);
}
}
}
break;
// pop up all the operators before the '(',push '+ -'
case '+':
case '-':
{
while (!opStack.empty())
{
if (!opStack.peek().getStringValue().equals("("))
{
OperatorObject op = opStack.pop();
postfixExp.add(op);
}else
{
break;
}
}
opStack.push(new OperatorObject(Character.toString(ch)));
}
break;
// pop up all the operators * / in stack,push '* /'
case '*':
case '/':
{
while (!opStack.empty())
{
String opStr = opStack.peek().getStringValue();
if (opStr.equals("*") || opStr.equals("/"))
{
OperatorObject op = opStack.pop();
postfixExp.add(op);
}else
{
break;
}
}
opStack.push(new OperatorObject(Character.toString(ch)));
}
break;
default:
{
// construct the number
if ((ch >= '0' && ch <= '9') || ch == '.')
{
String numStr = new String();
numStr = Character.toString(ch);
while ((i+1)<length)
{
ch = expStr.charAt(i + 1);
if ((ch >= '0' && ch <= '9') || ch == '.')
{
numStr += Character.toString(ch);
i++;
}else
{
break;
}
}
double num = Double.valueOf(numStr).doubleValue();
postfixExp.add(new NumberObject(num));
}
}
break;
}
}
// clear the stack of operators,push into vector
while (!opStack.empty())
{
postfixExp.add(opStack.pop());
}
}
/**
* get the value as per the post fix expression.
*/
public double calculate()
{
Stack<BulkObject> stack = new Stack<BulkObject>();
for (BulkObject ele : postfixExp)
{
if (ele instanceof NumberObject)
{
stack.push(ele);
}
if (ele instanceof OperatorObject)
{
// stack: bottom : num2,num1 : top
NumberObject num1 = (NumberObject)(stack.pop());
NumberObject num2 = (NumberObject)(stack.pop());
double num = getValue(num2,num1,(OperatorObject)ele);
stack.push(new NumberObject(num));
}
}
return ((NumberObject)(stack.peek())).getValue();
}
/**
*
*/
public double getValue(NumberObject num1,NumberObject num2,OperatorObject op)
{
String str = op.getValue();
double num = 0.0;
if (str.equals("+"))
{
num = num1.getValue() + num2.getValue();
}else
if (str.equals("-"))
{
num = num1.getValue() - num2.getValue();
}else
if (str.equals("*"))
{
num = num1.getValue() * num2.getValue();
}else
if (str.equals("/"))
{
num = num1.getValue() / num2.getValue();
}
return num;
}
}