中缀到后缀表达式的转换：java-stack实现

痛定思痛。 2022-06-12 14:59 183阅读 0赞

首先声明中缀表达式的要求，运算符只有+-\*/^和()这7种，其余只能是用来代表数字的小写字母，最后是=。

程序运行过程是，循环读取每个字符。

如果是操作数，那么就直接打印；

如果是操作符，则推入一个栈中同时进行判断。

判断过程：打印栈元素时，有一个优先级，^最高，其次\*/,再其次是+-，最小的是（。

如果新读取的操作符是^，那么需要循环出栈打印，优先级大于等于^的运算符，即只有^出栈，再把新的^入栈。

如果新读取的操作符是\*/，那么需要循环出栈打印，优先级大于等于\*/的运算符，即^\*/这三种都出栈，再把新的\*或/入栈。

如果新读取的操作符是\+-，那么需要循环出栈打印，优先级大于等于\+-的运算符，即\+-^\*/这五种都出栈，再把新的+或-入栈。

如果新读取的操作符是（，那么就直接入栈。

如果新读取的操作符是），那么就循环出栈打印栈顶元素，直到栈顶元素为（，这里）就不入栈了，且（出栈时也不打印。

把左括号的优先级设为最低的好处在于，除非是读取到了右括号，那么就不会移走栈中的左括号。这也符合中缀到后缀表达式的转换的要求。

package three;
    
    import java.util.Scanner;
    import java.util.Stack;
    
    public class toPostfix {
    
    	static void InFixToPostFix()
    	{
    	Stack<Character> s = new Stack<Character>();
    	String expression;
    	Character token;
    	int i=0;
    	Scanner sc = new Scanner(System.in);
    	expression = sc.next();
    	while ((token = expression.charAt(i++)) != '=')//只要字符串索引还没有到达=这个字符
    	{
    			if (token >= 'a' && token <= 'z')//如果是操作数，就输出
    			System.out.print(token + " ");
    			else//如果是运算符，就进行判断
    			{
    			switch (token)
    			{
    			case ')': while ( !s.empty() && s.peek() != '(' )//只要栈非空且栈顶元素非左括号就执行循环
    			{ System.out.print(s.pop() + " "); }//那么便打印出栈元素并删除
    			s.pop();//循环出栈到最后，栈顶是左括号，左括号并不需要打印
    			break;
    			
    			case '(': s.push(token);//如果是左括号，那么正常入栈
    			break;
    			
    			case '^': while ( !s.empty() && s.peek() == '^')//只要栈非空且栈顶元素是^，就执行循环
    			{ System.out.print(s.pop()+ " "); }
    			s.push(token);
    			break;
    			
    			case '*':
    			case '/': while ( !s.empty() && s.peek() != '+' &&
    			s.peek() != '-' && s.peek() != '(' )//只要栈非空且栈顶元素不是+不是-不是（即是乘除幂，就执行循环
    			{ System.out.print(s.pop()+ " "); }
    			s.push(token);
    			break;
    			
    			case '+':
    			case '-': while ( !s.empty() && s.peek() != '(' )//只要栈非空且栈顶元素不是（即是加减乘除幂，就执行循环
    			{ System.out.print(s.pop() + " "); }
    			s.push(token);
    			break;
    			
    			}
    			}
    	}
    	while (!s.empty())//如果上面循环都结束了栈还有元素，则弹出所有元素
    	{ System.out.print(s.pop()+ " "); }
    	
    	System.out.println();
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		InFixToPostFix();
    	}
    
    }

程序运行结果如下：

![20170725141559055][]

![20170725143832578][]

[20170725141559055]: /images/20220612/faf72d5b2c9d475885599d48e723a4e0.png
[20170725143832578]: /images/20220612/62de9c0cfb884235ba351865a66f22c6.png