欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

中缀表达式转换成后缀表达式,java栈实践

程序员文章站 2022-04-17 18:32:32
...

新手上路,不足之处希望大家指出,互相学习。

简单说一下思路:

1、把表达式放进数组。对此数组迭代。遇到数字直接放到String中,遇到+、-、*、/、(、)通过一定规则压入,压出栈。

2、简单说一下进栈、出栈的规则:

a、如果栈空,或者遇到(,直接将符号压进栈中。

b、出栈:栈顶的符号优先级一定最高,如果栈顶是*,遇到下一个符号是同级的*、/或者是优先级更低的+,-都需要先将*出栈,下一个符号再进栈。如果栈顶是+、-,下一个符号是*、/,则将*、/直接压进栈。

总之,栈中栈顶的优先级最高。

c、b中未讲()的情况,(压进栈中后不用管他,除非遇到),直接依次出栈,运算符号放进String中,(直接出栈不要管他。

最后、新手上路,写的不清楚的地方还请多多包涵,指正。

package com.zhu.algorithms.chapter3;

import java.util.Stack;

public class InfixToSuffix 
{
	/**
	 * 中缀转化成后缀。
	 * @author Fancy
	 */
	
	public static void main(String[] args) {
		String m = "a*b-w+s";
		String n = "a*(b-c)";
		String m1 = change( m );
		String n1 = change( n );
		System.out.println( m + " 后缀为 " + m1 );
		System.out.println( n + " 后缀为 " + n1 );
		
	}
	
	public static int valueOf( char x )
	{
		if( x == '+' || x == '-')
			return 1;
		else if( x == '*' || x == '/' )
			return 2;
		else
			return 0;
	}
	
	public static  String change( String m )
	{
		Stack<Character> stack = new Stack();
		char[] mChar = m.toCharArray();
		String suffix = "";
		
		for( int i = 0; i < mChar.length; i++)
		{
			char current = mChar[i];
			if( current == '+' || current == '-' || current == '*' || current == '/' )
			{
				if( stack.isEmpty() )
				{
					stack.push( current );
				}
				else
				{
					if( stack.peek() != '(')
					{
			
						while( valueOf( current ) <= valueOf( stack.peek() ) )
						{
							suffix = suffix + stack.peek();
							stack.pop();
							if( stack.isEmpty() )
								break;
						}
						
						
						stack.push( current );
					}
					else
						stack.push( current );
				}
			}
			else if( current == '(' )
			{
				stack.push( current );
			}
			else if( current == ')' )
			{
				while( stack.peek() != '(' )
				{
					suffix = suffix + stack.peek();
					stack.pop();
				}
				stack.pop();
			}
			else
				suffix = suffix + current;
		}
		
		while( !stack.isEmpty() )
		{
			suffix = suffix + stack.peek();
			stack.pop();
		}
		return suffix;
		
	}

}