中缀表达式变换为后缀表达式

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

操作数写至输出

左括号推入栈

右括号栈非空时，重复以下步骤

弹出一项，

若不为左括号，则opTop写至输出

若为左括号，则退出循环

当前读取的操作符opThis 若栈为空，则存入栈

若非空，重复以下步骤

弹出一项opTop

若为左括号，则左括号和当前操作符都存入栈，退出循环

若为操作符，且

若opTop>=opThis，则opTop存入栈，输出opThis

若opTop<opThis 则输出opTop

没有更多项当栈非空时，弹出项目，将其输出

public String doTrans() // do translation to postfix
	{
		for (int j = 0; j < input.length(); j++) // for each char
		{
			char ch = input.charAt(j); // get it
			theStack.displayStack("For " + ch + " "); // *diagnostic*
			switch (ch) {
			case '+': // it's + or -
			case '-':
				gotOper(ch, 1); // go pop operators
				break; // (precedence 1)
			case '*': // it's * or /
			case '/':
				gotOper(ch, 2); // go pop operators
				break; // (precedence 2)
			case '(': // it's a left paren
				theStack.push(ch); // push it
				break;
			case ')': // it's a right paren
				gotParen(ch); // go pop operators
				break;
			default: // must be an operand
				output = output + ch; // write it to output
				break;
			} // end switch
		} // end for
		while (!theStack.isEmpty()) // pop remaining opers
		{
			theStack.displayStack("While "); // *diagnostic*
			output = output + theStack.pop(); // write to output
		}
		theStack.displayStack("End   "); // *diagnostic*
		return output; // return postfix
         }

public void gotOper(char opThis, int prec1) { // got operator from input
		while (!theStack.isEmpty()) {
			char opTop = theStack.pop();
			if (opTop == '(') // if it's a '('
			{
				theStack.push(opTop); // restore '('
				break;
			} else // it's an operator
			{
				int prec2; // precedence of new op

				if (opTop == '+' || opTop == '-') // find new op prec
					prec2 = 1;
				else
					prec2 = 2;
				if (prec2 < prec1) // if prec of new op less
				{ // than prec of old
					theStack.push(opTop); // save newly-popped op
					break;
				} else
					// prec of new not less
					output = output + opTop; // than prec of old
			} // end else (it's an operator)
		} // end while
		theStack.push(opThis); // push new operator
        }

	public void gotParen(char ch) { // got right paren from input
		while (!theStack.isEmpty()) {
			char chx = theStack.pop();
			if (chx == '(') // if popped '('
				break; // we're done
			else
				// if popped operator
				output = output + chx; // output it
		} // end while
	} // end popOps()124+5*+
	// --------------------------
} // end class InToPost

中缀表达式变换为后缀表达式

相关推荐