栈应用（如何实现后缀表达式（代码实现）） _中缀表达式

本文概述

C ++
C
Java
python
C#

中缀表达式：
形式为op b的表达式。当运算符位于每对操作数之间时。
【栈应用（如何实现后缀表达式（代码实现））】后缀表达式：
形式为b op的表达式。每对操作数都遵循一个运算符时。
为什么用后缀表示表达式？
编译器从左到右或从右到左扫描表达式。
考虑以下表达式：a op1 b op2 c op3 d
如果op1 = +, op2 = *, op3 = +
编译器首先扫描表达式以评估表达式b * c, 然后再次扫描表达式以为其添加a。然后将结果添加到另一次扫描后的d中。
重复扫描使其效率很低。最好在求值前将表达式转换为后缀(或前缀)形式。
后缀形式的对应表达式为：abc * + d +。可以使用栈轻松地评估后缀表达式。我们将在另一篇文章中介绍postfix表达式评估。
算法
1.
从左到右扫描中缀表达式。
2.
如果扫描的字符是操作数, 则将其输出。
3.
其他,
1
如果已扫描运算符的优先级大于栈中运算符的优先级(或者栈为空, 或者栈中包含"("), 则将其压入。
2
否则, 从栈中弹出所有大于或等于已扫描运算符的运算符。完成之后, 将扫描的运算符推入栈。 (如果在弹出时遇到括号, 请停在该位置, 然后将已扫描的运算符推入栈。)
4.
如果扫描的字符是"(", 则将其推入栈。
5.
如果扫描的字符是')', 则弹出栈并输出, 直到遇到'(', 然后都放弃括号。
6.
重复步骤2-6, 直到扫描了中缀表达式。
7.
打印输出
8.
从栈弹出并输出, 直到不为空。
以下是上述算法的实现
C ++

/* C++ implementation to convert infix expression to postfix*/ // Note that here we use std::stack // for Stack operations #include< bits/stdc++.h> using namespace std; //Function to return precedence of operators int prec( char c) { if (c == '^' ) return 3; else if (c == '*' || c == '/' ) return 2; else if (c == '+' || c == '-' ) return 1; else return -1; } // The main function to convert infix expression //to postfix expression void infixToPostfix(string s) { std::stack< char > st; st.push( 'N' ); int l = s.length(); string ns; for ( int i = 0; i < l; i++) {// If the scanned character is // an operand, add it to output string. if ((s[i] > = 'a' & & s[i] < = 'z' ) || (s[i] > = 'A' & & s[i] < = 'Z' )) ns+=s[i]; // If the scanned character is an // ‘(‘, push it to the stack. else if (s[i] == '(' )st.push( '(' ); // If the scanned character is an ‘)’, // pop and to output string from the stack // until an ‘(‘ is encountered. else if (s[i] == ')' ) { while (st.top() != 'N' & & st.top() != '(' ) { char c = st.top(); st.pop(); ns += c; } if (st.top() == '(' ) { char c = st.top(); st.pop(); } }//If an operator is scanned else { while (st.top() != 'N' & & prec(s[i]) < = prec(st.top())) { char c = st.top(); st.pop(); ns += c; } st.push(s[i]); } }// Pop all the remaining elements from the stack while (st.top() != 'N' ) { char c = st.top(); st.pop(); ns += c; }cout < < ns < < endl; } //Driver program to test above functions int main() { string exp = "a+b*(c^d-e)^(f+g*h)-i" ; infixToPostfix( exp ); return 0; } // This code is contributed by Gautam Singh

// C program to convert infix expression to postfix #include < stdio.h> #include < string.h> #include < stdlib.h> // Stack type struct Stack { int top; unsigned capacity; int * array; }; // Stack Operations struct Stack* createStack( unsigned capacity ) { struct Stack* stack = ( struct Stack*) malloc ( sizeof ( struct Stack)); if (!stack) return NULL; stack-> top = -1; stack-> capacity = capacity; stack-> array = ( int *) malloc (stack-> capacity * sizeof ( int )); return stack; } int isEmpty( struct Stack* stack) { return stack-> top == -1 ; } char peek( struct Stack* stack) { return stack-> array[stack-> top]; } char pop( struct Stack* stack) { if (!isEmpty(stack)) return stack-> array[stack-> top--] ; return '$' ; } void push( struct Stack* stack, char op) { stack-> array[++stack-> top] = op; } // A utility function to check if // the given character is operand int isOperand( char ch) { return (ch > = 'a' & & ch < = 'z' ) || (ch > = 'A' & & ch < = 'Z' ); } // A utility function to return // precedence of a given operator // Higher returned value means // higher precedence int Prec( char ch) { switch (ch) { case '+' : case '-' : return 1; case '*' : case '/' : return 2; case '^' : return 3; } return -1; } // The main function that // converts given infix expression // to postfix expression. int infixToPostfix( char * exp ) { int i, k; // Create a stack of capacity // equal to expression size struct Stack* stack = createStack( strlen ( exp )); if (!stack) // See if stack was created successfully return -1 ; for (i = 0, k = -1; exp [i]; ++i) {// If the scanned character is // an operand, add it to output. if (isOperand( exp [i])) exp [++k] = exp [i]; // If the scanned character is an // ‘(‘, push it to the stack. else if ( exp [i] == '(' ) push(stack, exp [i]); // If the scanned character is an ‘)’, // pop and output from the stack // until an ‘(‘ is encountered. else if ( exp [i] == ')' ) { while (!isEmpty(stack) & & peek(stack) != '(' ) exp [++k] = pop(stack); if (!isEmpty(stack) & & peek(stack) != '(' ) return -1; // invalid expression else pop(stack); } else // an operator is encountered { while (!isEmpty(stack) & & Prec( exp [i]) < = Prec(peek(stack))) exp [++k] = pop(stack); push(stack, exp [i]); } } // pop all the operators from the stack while (!isEmpty(stack)) exp [++k] = pop(stack ); exp [++k] = '\0' ; printf ( "%s" , exp ); } // Driver program to test above functions int main() { char exp [] = "a+b*(c^d-e)^(f+g*h)-i" ; infixToPostfix( exp ); return 0; }

Java

/* Java implementation to convert infix expression to postfix*/ // Note that here we use Stack class for Stack operations import java.util.Stack; class Test {// A utility function to return // precedence of a given operator // Higher returned value means // higher precedence static int Prec( char ch) { switch (ch) { case '+' : case '-' : return 1 ; case '*' : case '/' : return 2 ; case '^' : return 3 ; } return - 1 ; }// The main method that converts // given infix expression // to postfix expression. static String infixToPostfix(String exp) { // initializing empty String for result String result = new String( "" ); // initializing empty stack Stack< Character> stack = new Stack< > (); for ( int i = 0 ; i< exp.length(); ++i) { char c = exp.charAt(i); // If the scanned character is an // operand, add it to output. if (Character.isLetterOrDigit(c)) result += c; // If the scanned character is an '(', // push it to the stack. else if (c == '(' ) stack.push(c); //If the scanned character is an ')', // pop and output from the stack // until an '(' is encountered. else if (c == ')' ) { while (!stack.isEmpty() & & stack.peek() != '(' ) result += stack.pop(); stack.pop(); } else // an operator is encountered { while (!stack.isEmpty() & & Prec(c) < = Prec(stack.peek())){result += stack.pop(); } stack.push(c); }}// pop all the operators from the stack while (!stack.isEmpty()){ if (stack.peek() == '(' ) return "Invalid Expression" ; result += stack.pop(); } return result; }// Driver method public static void main(String[] args) { String exp = "a+b*(c^d-e)^(f+g*h)-i" ; System.out.println(infixToPostfix(exp)); } }

python

# Python program to convert infix expression to postfix # Class to convert the expression class Conversion:# Constructor to initialize the class variables def __init__( self , capacity): self .top = - 1 self .capacity = capacity # This array is used a stack self .array = [] # Precedence setting self .output = [] self .precedence = { '+' : 1 , '-' : 1 , '*' : 2 , '/' : 2 , '^' : 3 }# check if the stack is empty def isEmpty( self ): return True if self .top = = - 1 else False# Return the value of the top of the stack def peek( self ): return self .array[ - 1 ]# Pop the element from the stack def pop( self ): if not self .isEmpty(): self .top - = 1 return self .array.pop() else : return "$"# Push the element to the stack def push( self , op): self .top + = 1 self .array.append(op) # A utility function to check is the given character # is operand def isOperand( self , ch): return ch.isalpha() # Check if the precedence of operator is strictly # less than top of stack or not def notGreater( self , i): try : a = self .precedence[i] b = self .precedence[ self .peek()] return True if a< = b else False except KeyError: return False# The main function that # converts given infix expression # to postfix expression def infixToPostfix( self , exp):# Iterate over the expression for conversion for i in exp: # If the character is an operand, # add it to output if self .isOperand(i): self .output.append(i)# If the character is an '(', push it to stack elif i= = '(' : self .push(i) # If the scanned character is an ')', pop and # output from the stack until and '(' is found elif i = = ')' : while ( ( not self .isEmpty()) and self .peek() ! = '(' ): a = self .pop() self .output.append(a) if ( not self .isEmpty() and self .peek() ! = '(' ): return - 1 else : self .pop() # An operator is encountered else : while ( not self .isEmpty() and self .notGreater(i)): self .output.append( self .pop()) self .push(i) # pop all the operator from the stack while not self .isEmpty(): self .output.append( self .pop()) print "".join( self .output) # Driver program to test above function exp = "a+b*(c^d-e)^(f+g*h)-i" obj = Conversion( len (exp)) obj.infixToPostfix(exp) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

using System; using System.Collections.Generic; /* c# implementation to convert infix expression to postfix*/ // Note that here we use Stack // class for Stack operations publicclass Test {// A utility function to return // precedence of a given operator // Higher returned value means higher precedence internal static int Prec( char ch) { switch (ch) { case '+' : case '-' : return 1; case '*' : case '/' : return 2; case '^' : return 3; } return -1; } // The main method that converts given infix expression // to postfix expression. public static string infixToPostfix( string exp) { // initializing empty String for result string result = "" ; // initializing empty stack Stack< char > stack = new Stack< char > (); for ( int i = 0; i < exp.Length; ++i) { char c = exp[i]; // If the scanned character is an // operand, add it to output. if ( char .IsLetterOrDigit(c)) { result += c; } // If the scanned character is an '(', // push it to the stack. else if (c == '(' ) { stack.Push(c); } //If the scanned character is an ')', // pop and output from the stack // until an '(' is encountered. else if (c == ')' ) { while (stack.Count > 0 & & stack.Peek() != '(' ) { result += stack.Pop(); } if (stack.Count > 0 & & stack.Peek() != '(' ) { return "Invalid Expression" ; // invalid expression } else { stack.Pop(); } } else // an operator is encountered { while (stack.Count > 0 & & Prec(c) < = Prec(stack.Peek())) { result += stack.Pop(); } stack.Push(c); } } // pop all the operators from the stack while (stack.Count > 0) { result += stack.Pop(); } return result; } // Driver method public static void Main( string [] args) { string exp = "a+b*(c^d-e)^(f+g*h)-i" ; Console.WriteLine(infixToPostfix(exp)); } } // This code is contributed by Shrikant13

输出如下：