用Java实现的一个逆波兰表达式计算的小demo
public class NiBoLan {
/**
* @param args
*/
public static void main(String[] args) {
// String str = "1 + ( 2 - 3 ) * 4 + 10 / 5";
String str = "2 * 3 + 6 / 2 * ( 3 - 2 ) + 4";
String[] strings = str.split(" ");
String[] result = middleToLast(strings);
int aa = calculate(result);
System.out.println(aa);
}
/**
* 将后缀表达式通过栈结构计算出最终结果
* @param strings
* @return
*/
private static int calculate(String[] strings){
Stack<Integer> stack = new Stack<Integer>(strings.length);
for (int i = 0; i < strings.length; i++) {
String str = strings[i];
if(str != null){
if("+".equals(str)){
int a = stack.pop();
int b = stack.pop();
stack.push(b + a);
}else if("-".equals(str)){
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
}else if("*".equals(str)){
int a = stack.pop();
int b = stack.pop();
stack.push(b * a);
}else if("/".equals(str)){
int a = stack.pop();
int b = stack.pop();
stack.push(b / a);
}else{
// 是数字，直接入栈
stack.push(Integer.parseInt(str));
}
}
}
return stack.pop();
}
/**
* 通过栈结构将中缀表达式转换成后缀表达式
* @param strings
* @return
*/
private static String[] middleToLast(String[] strings) {
Stack<String> stack = new Stack<String>(strings.length);
String [] result = new String[strings.length];
int resultCount = 0;
for (int i = 0; i < strings.length; i++) {
String str = strings[i];
// 遍历过程中如果要加入栈顶的符号是+或者-，如果栈为空，则直接添加，如果不为空，因为+ 和 -比+ - * / 的优先级都小。所以
// 将当前栈顶符号pop出栈放入到结果中，继续判断当前栈顶是否为空，继续弹栈，直到栈为null为止
if("+".equals(str) || "-".equals(str)){
if(!stack.isEmpty()){
while("+".equals(stack.peek())
|| "-".equals(stack.peek())
||"*".equals(stack.peek())
||"/".equals(stack.peek())){
String pop = stack.pop();
result[resultCount++] = pop;
}
}
stack.push(str);
}else if("*".equals(str) || "/".equals(str)){
// 遍历过程中如果要加入栈顶的符号是*或者/ 判断当前栈顶符号是否也为* /， 如果为* /，就要弹栈加入结果集，并继续判断
while("*".equals(stack.peek())||"/".equals(stack.peek())){
String pop = stack.pop();
result[resultCount++] = pop;
}
stack.push(str);
}else if("(".equals(str)){
// 左括号直接入栈
stack.push(str);
}else if(")".equals(str)){
// 将到上一个左括号的符号弹栈加入结果集
while(!"(".equals(stack.peek())){
result[resultCount++] = stack.pop();
}
stack.pop();
}else{
// 是数字，直接加入结果集
result[resultCount++] = str;
}
}
// 遍历完毕，没有元素需要判断了，将栈中元素依次弹出放入结果集中
while(!stack.isEmpty()){
result[resultCount++] = stack.pop();
}
return result;
}
/**
* 自定义栈结构
* @author youtl
*
* @param <T>
*/
static class Stack<T>{
private Object [] data;
private int top = -1;
public Stack(int length){
data = new Object[length];
}
public T push(T t){
addElement(t);
return t;
}
public T pop(){
if(top < 0){
return null;
}
T t = (T) data[top];
data[top] = null;
top--;
return t;
}
public T peek(){
if(top < 0){
return null;
}
return (T) data[top];
}
private void addElement(T t) {
data[++top] = t;
}
public int getLength(){
return (top+1);
}
public boolean isEmpty(){
return (top+1) > 0 ? false : true;
}
public void printStack(){
while(!isEmpty()){
System.out.println(pop());
}
}
}
}
