java中缀表达式转为后缀表达式

谁践踏了优雅 2022-06-01 00:43 249阅读 0赞

日常生活中，我们使用的数学表达式为中缀表达式 例如 6 + 3 \* ( 9 - 7 ) - 8 / 2。

后缀表达式的写法将运算符放在数字之后如 6397-\*+82/- 可以看到在后缀表达式中，省去了括号。计算机采用的就是这种计算方式。

## 利用栈实现将中缀表达式转换为后缀表达式： ##

逻辑：

1、如果字符串是数字就直接输出

2、如果字符串是运算符号：1）如果栈为空则将运算符压入栈 2）栈不为空，循环比较运算符与栈顶的运算符进行优先级，若栈顶运算符等级大于等于字符串运算符等级，则将栈顶的运算符弹出，循环结束将运算符压入栈中。

3、如果字符串为"("：直接将字符串压入栈

4、如果字符串为")":  循环弹出栈顶元素，直到弹出"("

5、如果最终所有数字输出完，栈不为空则将所有元素依次弹出

运算符等级的设定：

( : 0

\+ = :1

\* / :2

举例：6 + 3 \* ( 9 - 7 ) - 8 / 2

步骤一：6   是数字（逻辑1、），直接输出

*结果：6           栈内：*

步骤二：+   是运算符（逻辑2、1） ），压入栈

*结果：6           栈内：+*

步骤三：3   是数字（逻辑1、），直接输出

*结果：63         栈内：+*

步骤四：\*   是运算符（逻辑2、2） ）压入栈

结果：63         栈内：+\*

步骤五：(   是左括号 （逻辑3)   压入栈

结果：63         栈内： +\*(

步骤六：9  是数字（逻辑1、），直接输出

结果：639         栈内： +\*(

步骤七：-   是运算符（逻辑2、1） ），压入栈

结果：63         栈内： +\*(-

步骤八：7  是数字（逻辑1、），直接输出

结果：6397         栈内： +\*(-

步骤九： )  是右括号 （逻辑4）循环弹栈顶元素直到遇到左括号  （左括号不打印）

结果：6397-        栈内： +\*

步骤十： -  是运算符   （逻辑2、2） 循环比较弹栈顶元素 最后压入栈

结果：6397-\*+         栈内： -

步骤十一 8 是数字（逻辑1、），直接输出

结果：6397-\*+8          栈内： -

步骤十二 /是运算符（逻辑2、1） ），压入栈

结果：6397-\*+8          栈内： \-/

步骤十三：2 是数字（逻辑1、） 直接输出

结果：6397-\*+82         栈内：\-/

步骤十四：逻辑5、 弹空栈

结果：6397-\*+82/-         栈内：

java代码：

package stack;
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * 
     * @ClassName: Stack
     * @Description: 栈的实现并且完成中缀表达式转换后缀表达式 
     * @author xiaomu
     * @date 2018年1月15日 下午9:00:09
     * 
     * @param <T>
     */
    public class Stack<T> {
    	private static final Map<String, Integer> basic = new HashMap<String, Integer>();
    	static {
    		basic.put("-", 1);
    		basic.put("+", 1);
    		basic.put("*", 2);
    		basic.put("/", 2);
    		basic.put("(", 0);// 在运算中 （）的优先级最高，但是此处因程序中需要 故设置为0
    	}
    	private final static int INIT_SIZE = 100;
    	private int size = 0;
    	private Object[] elementData;
    
    	public Stack() {
    		this(INIT_SIZE);
    	}
    
    	public Stack(int size) {
    		elementData = new Object[size];
    	}
    
    	public void clearStack() {
    		while (size > 1) {
    			pop();
    		}
    	}
    
    	public boolean stackEmpty() {
    		return 0 == size;
    	}
    
    	public boolean stackFull() {
    		return elementData.length == size;
    	}
    
    	public void push(T elem) {
    		if (stackFull()) {
    			System.err.println("栈满");
    			return;
    		}
    		elementData[size++] = elem;
    	}
    
    	public T pop() {
    		if (stackEmpty()) {
    			System.err.println("栈已经空了");
    			return null;
    		}
    		T elem = getTop();
    		size--;
    		return elem;
    	}
    
    	public int stackLength() {
    		return size;
    	}
    
    	public T getTop() {
    		if (stackEmpty()) {
    			return null;
    		}
    		return (T) elementData[size - 1];
    	}
    
    	public static boolean isNumeric00(String str) {
    		try {
    			Integer.parseInt(str);
    			return true;
    		} catch (NumberFormatException e) {
    			// System.out.println("异常：\"" + str + "\"不是数字/整数...");
    			return false;
    		}
    	}
    
    	public boolean comp(String str) {
    		String top = (String) getTop();
    		if ("(".equals(top) || null == top) {
    			return false;
    		}
    
    		if (basic.get(str) <= basic.get(top)) {
    			return true;
    		}
    		return false;
    
    	}
    
    	/**
    	 * 6397-*+82/-
    	 */
    	public static void main(String[] args) {
    		Stack<String> stack = new Stack<String>();
    		String str = "6 + 3 * ( 9 - 7 ) - 8 / 2";
    		String str1[] = str.split(" ");
    		for (String s : str1) {
    			if (isNumeric00(s)) {
    				System.out.print(s);
    				continue;
    			}
    
    			if ("(".equals(s)) {
    				stack.push(s);
    				continue;
    			}
    			if (")".equals(s)) {
    				String temp;
    				while (!(temp = stack.pop()).equals("(")) {
    					System.out.print(temp);
    				}
    				continue;
    			}
    			if (stack.stackEmpty()) {
    				stack.push(s);
    				continue;
    			}
    			while (stack.comp(s)) {
    				System.out.print(stack.pop());
    			}
    			stack.push(s);
    
    		}
    		while (!stack.stackEmpty()) {
    			System.out.print(stack.pop());
    		}
    	}
    }

本代码还有不足之处：

1、对字符串的处理只使用了一个split来进行分割，太过于局限性。

2、本代码只是完成了中缀表达式转换后缀表达式，并没有进行计算结果。

3、对于自己手写的栈，没有加入动态扩充的功能，所以依赖于创建时候按照需求自己定义大小

作者将在改进后连同计算思路再发一篇新的学习心得，敬请关注。