栈应用：如何实现后缀表达式？代码实现

本文概述

• 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

// 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)

C#

using System;
using System.Collections.Generic;
 
/* c# implementation to convert
infix expression to postfix*/
// Note that here we use Stack
// class for Stack operations
 
public  class 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

输出如下： 

abcd^e-fgh*+^*+i-

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。