中缀表达式转换成后缀表达式,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; } }