本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• C ++
• C
• Java
• python
• C#
• C ++
• C
• Java
• C#
• python

后缀表示法用于表示代数表达式。与后缀形式相比, 以后缀形式编写的表达式的求值速度更快后缀不需要括号中的括号表示法。我们已经讨论过后缀到后缀的转换。在这篇文章中, 讨论了后缀表达式的评估。
以下是评估后缀表达式的算法。
1)创建一个堆栈来存储操作数(或值)。
2)扫描给定的表达式, 然后对每个扫描的元素执行以下操作。
…..a)如果元素是数字, 则将其推入堆栈
…..b)如果元素是运算符, 请从堆栈中弹出该运算符的操作数。评估运算符并将结果推回堆栈
3)表达式结束时, 堆栈中的数字是最终答案
例子：
令给定的表达式为" 2 3 1 * + 9-"。我们一一扫描所有元素。
1)扫描" 2", 它是一个数字, 因此将其压入堆栈。堆叠中包含" 2"
2)扫描" 3", 再次扫描一个数字, 将其推入堆栈, 堆栈现在包含" 2 3"(从下到上)
3)扫描" 1", 再扫描一个数字, 将其推入堆栈, 堆栈现在包含" 2 3 1"
4)扫描" *", 它是一个运算符, 从堆栈中弹出两个操作数, 将*运算符应用于操作数, 我们得到3 * 1, 结果为3。将结果" 3"压入堆栈。堆叠现在变为" 2 3"。
5)扫描" +", 它是一个运算符, 从堆栈中弹出两个操作数, 将+运算符应用于操作数, 我们得到3 + 2, 结果为5。将结果" 5"压入堆栈。堆叠现在变为" 5"。
6)扫描" 9", 它是一个数字, 我们将其压入堆栈。堆叠现在变为" 5 9"。
7)扫描"-", 它是一个运算符, 从堆栈中弹出两个操作数, 将–运算符应用于操作数, 我们得到5 – 9, 结果为-4。我们将结果" -4"推入堆栈。堆叠现在变为" -4"。
8)没有更多要扫描的元素, 我们从堆栈中返回顶部元素(这是堆栈中剩下的唯一元素)。
推荐：请在"实践首先, 在继续解决方案之前。下面是上述算法的实现。
C ++

// C++ program to evaluate value of a postfix expression #include < iostream> #include < string.h> using namespace std; // 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 )); if (!stack-> array) return NULL; 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; } // The main function that returns value of a given postfix expression int evaluatePostfix( char * exp ) { // Create a stack of capacity equal to expression size struct Stack* stack = createStack( strlen ( exp )); int i; // See if stack was created successfully if (!stack) return -1; // Scan all characters one by one for (i = 0; exp [i]; ++i) { // If the scanned character is an operand (number here), // push it to the stack. if ( isdigit ( exp [i])) push(stack, exp [i] - '0' ); // If the scanned character is an operator, pop two // elements from stack apply the operator else { int val1 = pop(stack); int val2 = pop(stack); switch ( exp [i]) { case '+' : push(stack, val2 + val1); break ; case '-' : push(stack, val2 - val1); break ; case '*' : push(stack, val2 * val1); break ; case '/' : push(stack, val2/val1); break ; } } } return pop(stack); } // Driver program to test above functions int main() { char exp [] = "231*+9-" ; cout< < "postfix evaluation: " < < evaluatePostfix( exp ); return 0; }

C

// C program to evaluate value of a postfix expression #include < stdio.h> #include < string.h> #include < ctype.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 )); if (!stack-> array) return NULL; 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; }// The main function that returns value of a given postfix expression int evaluatePostfix( char * exp ) { // Create a stack of capacity equal to expression size struct Stack* stack = createStack( strlen ( exp )); int i; // See if stack was created successfully if (!stack) return -1; // Scan all characters one by one for (i = 0; exp [i]; ++i) { // If the scanned character is an operand (number here), // push it to the stack. if ( isdigit ( exp [i])) push(stack, exp [i] - '0' ); // If the scanned character is an operator, pop two // elements from stack apply the operator else { int val1 = pop(stack); int val2 = pop(stack); switch ( exp [i]) { case '+' : push(stack, val2 + val1); break ; case '-' : push(stack, val2 - val1); break ; case '*' : push(stack, val2 * val1); break ; case '/' : push(stack, val2/val1); break ; } } } return pop(stack); }// Driver program to test above functions int main() { char exp [] = "231*+9-" ; printf ( "postfix evaluation: %d" , evaluatePostfix( exp )); return 0; }

Java

// Java proram to evaluate value of a postfix expressionimport java.util.Stack; public class Test { // Method to evaluate value of a postfix expression static int evaluatePostfix(String exp) { //create a stack Stack< Integer> stack= new Stack< > (); // Scan all characters one by one for ( int i= 0 ; i< exp.length(); i++) { char c=exp.charAt(i); // If the scanned character is an operand (number here), // push it to the stack. if (Character.isDigit(c)) stack.push(c - '0' ); //If the scanned character is an operator, pop two // elements from stack apply the operator else { int val1 = stack.pop(); int val2 = stack.pop(); switch (c) { case '+' : stack.push(val2+val1); break ; case '-' : stack.push(val2- val1); break ; case '/' : stack.push(val2/val1); break ; case '*' : stack.push(val2*val1); break ; } } } return stack.pop(); }// Driver program to test above functions public static void main(String[] args) { String exp= "231*+9-" ; System.out.println( "postfix evaluation: " +evaluatePostfix(exp)); } } // Contributed by Sumit Ghosh

python

# Python program to evaluate value of a postfix expression# Class to convert the expression class Evaluate:# Constructor to initialize the class variables def __init__( self , capacity): self .top = - 1 self .capacity = capacity # This array is used a stack self .array = []# 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) # The main function that converts given infix expression # to postfix expression def evaluatePostfix( self , exp):# Iterate over the expression for conversion for i in exp:# If the scanned character is an operand # (number here) push it to the stack if i.isdigit(): self .push(i)# If the scanned character is an operator, # pop two elements from stack and apply it. else : val1 = self .pop() val2 = self .pop() self .push( str ( eval (val2 + i + val1)))return int ( self .pop())# Driver program to test above function exp = "231*+9-" obj = Evaluate( len (exp)) print "postfix evaluation: %d" % (obj.evaluatePostfix(exp)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# proram to evaluate value of a postfix expression using System; using System.Collections; namespace GFG { class Geek { //Main() method static void Main() { Geek e = new Geek(); e.v = ( "231*+9-" ); e.expression(); Console.WriteLine( "postfix evaluation: " + e.answer); Console.Read(); }public string v; //'v' is variable to store the string valuepublic string answer; Stack i = new Stack(); //'Stack()' is inbuilt function for namespace 'System.Collections'public void expression() //evaluation method { int a, b, ans; for ( int j = 0; j < v.Length; j++) //'v.Length' means length of the string { String c = v.Substring(j, 1); if (c.Equals( "*" )) { String sa = (String)i.Pop(); String sb = (String)i.Pop(); a = Convert.ToInt32(sb); b = Convert.ToInt32(sa); ans = a * b; i.Push(ans.ToString()); } else if (c.Equals( "/" )) { String sa = (String)i.Pop(); String sb = (String)i.Pop(); a = Convert.ToInt32(sb); b = Convert.ToInt32(sa); ans = a / b; i.Push(ans.ToString()); } else if (c.Equals( "+" )) { String sa = (String)i.Pop(); String sb = (String)i.Pop(); a = Convert.ToInt32(sb); b = Convert.ToInt32(sa); ans = a + b; i.Push(ans.ToString()); } else if (c.Equals( "-" )) { String sa = (String)i.Pop(); String sb = (String)i.Pop(); a = Convert.ToInt32(sb); b = Convert.ToInt32(sa); ans = a - b; i.Push(ans.ToString()); } else { i.Push(v.Substring(j, 1)); } } answer = (String)i.Pop(); } } }

输出如下：

postfix evaluation: -4

评估算法的时间复杂度为O(n), 其中n是输入表达式中的字符数。
上述实施方式存在以下局限性。
1)它仅支持4个二进制运算符" +", " *", "-"和" /"。通过添加更多的开关盒, 可以将其扩展为更多的操作员。
2)允许的操作数仅是一位数字操作数。通过在给定表达式的所有元素(运算符和操作数)之间添加空格之类的分隔符, 可以将该程序扩展为多个数字。
下面给出的是扩展程序, 该程序允许具有多个数字的操作数。
C ++

// CPP program to evaluate value of a postfix // expression having multiple digit operands #include < bits/stdc++.h> using namespace std; // Stack type class Stack { public : int top; unsigned capacity; int * array; }; // Stack Operations Stack* createStack( unsigned capacity ) { Stack* stack = new Stack(); if (!stack) return NULL; stack-> top = -1; stack-> capacity = capacity; stack-> array = new int [(stack-> capacity * sizeof ( int ))]; if (!stack-> array) return NULL; return stack; } int isEmpty(Stack* stack) { return stack-> top == -1 ; } int peek(Stack* stack) { return stack-> array[stack-> top]; } int pop(Stack* stack) { if (!isEmpty(stack)) return stack-> array[stack-> top--] ; return '$' ; } void push(Stack* stack, int op) { stack-> array[++stack-> top] = op; } // The main function that returns value // of a given postfix expression int evaluatePostfix( char * exp ) { // Create a stack of capacity equal to expression size Stack* stack = createStack( strlen ( exp )); int i; // See if stack was created successfully if (!stack) return -1; // Scan all characters one by one for (i = 0; exp [i]; ++i) { //if the character is blank space then continue if ( exp [i] == ' ' ) continue ; // If the scanned character is an // operand (number here), extract the full number // Push it to the stack. else if ( isdigit ( exp [i])) { int num=0; //extract full number while ( isdigit ( exp [i])) { num = num * 10 + ( int )( exp [i] - '0' ); i++; } i--; //push the element in the stack push(stack, num); } // If the scanned character is an operator, pop two // elements from stack apply the operator else { int val1 = pop(stack); int val2 = pop(stack); switch ( exp [i]) { case '+' : push(stack, val2 + val1); break ; case '-' : push(stack, val2 - val1); break ; case '*' : push(stack, val2 * val1); break ; case '/' : push(stack, val2/val1); break ; } } } return pop(stack); } // Driver code int main() { char exp [] = "100 200 + 2 / 5 * 7 +" ; cout < < evaluatePostfix( exp ); return 0; } // This code is contributed by rathbhupendra

C

// C program to evaluate value of a postfix // expression having multiple digit operands #include < stdio.h> #include < string.h> #include < ctype.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 )); if (!stack-> array) return NULL; return stack; }int isEmpty( struct Stack* stack) { return stack-> top == -1 ; }int peek( struct Stack* stack) { return stack-> array[stack-> top]; }int pop( struct Stack* stack) { if (!isEmpty(stack)) return stack-> array[stack-> top--] ; return '$' ; }void push( struct Stack* stack, int op) { stack-> array[++stack-> top] = op; }// The main function that returns value // of a given postfix expression int evaluatePostfix( char * exp ) { // Create a stack of capacity equal to expression size struct Stack* stack = createStack( strlen ( exp )); int i; // See if stack was created successfully if (!stack) return -1; // Scan all characters one by one for (i = 0; exp [i]; ++i) { //if the character is blank space then continue if ( exp [i]== ' ' ) continue ; // If the scanned character is an // operand (number here), extract the full number // Push it to the stack. else if ( isdigit ( exp [i])) { int num=0; //extract full number while ( isdigit ( exp [i])) { num=num*10 + ( int )( exp [i]- '0' ); i++; } i--; //push the element in the stack push(stack, num); }// If the scanned character is an operator, pop two // elements from stack apply the operator else { int val1 = pop(stack); int val2 = pop(stack); switch ( exp [i]) { case '+' : push(stack, val2 + val1); break ; case '-' : push(stack, val2 - val1); break ; case '*' : push(stack, val2 * val1); break ; case '/' : push(stack, val2/val1); break ; } } } return pop(stack); }// Driver program to test above functions int main() { char exp [] = "100 200 + 2 / 5 * 7 +" ; printf ( "%d" , evaluatePostfix( exp )); return 0; }// This code is contributed by Arnab Kundu

Java

// Java proram to evaluate value of a postfix // expression having multiple digit operands import java.util.Stack; class Test1 { // Method to evaluate value of a postfix expression static int evaluatePostfix(String exp) { //create a stack Stack< Integer> stack = new Stack< > (); // Scan all characters one by one for ( int i = 0 ; i < exp.length(); i++) { char c = exp.charAt(i); if (c == ' ' ) continue ; // If the scanned character is an operand // (number here), extract the number // Push it to the stack. else if (Character.isDigit(c)) { int n = 0 ; //extract the characters and store it in num while (Character.isDigit(c)) { n = n* 10 + ( int )(c- '0' ); i++; c = exp.charAt(i); } i--; //push the number in stack stack.push(n); }// If the scanned character is an operator, pop two // elements from stack apply the operator else { int val1 = stack.pop(); int val2 = stack.pop(); switch (c) { case '+' : stack.push(val2+val1); break ; case '-' : stack.push(val2- val1); break ; case '/' : stack.push(val2/val1); break ; case '*' : stack.push(val2*val1); break ; } } } return stack.pop(); }// Driver program to test above functions public static void main(String[] args) { String exp = "100 200 + 2 / 5 * 7 +" ; System.out.println(evaluatePostfix(exp)); } }// This code is contributed by Arnab Kundu

C#

// C# proram to evaluate value of a postfix // expression having multiple digit operands using System; using System.Collections.Generic; class GFG { // Method to evaluate value of // a postfix expression public static int evaluatePostfix( string exp) { // create a stack Stack< int > stack = new Stack< int > (); // Scan all characters one by one for ( int i = 0; i < exp.Length; i++) { char c = exp[i]; if (c == ' ' ) { continue ; }// If the scanned character is an // operand (number here), extract // the number. Push it to the stack. else if ( char .IsDigit(c)) { int n = 0; // extract the characters and // store it in num while ( char .IsDigit(c)) { n = n * 10 + ( int )(c - '0' ); i++; c = exp[i]; } i--; // push the number in stack stack.Push(n); }// If the scanned character is // an operator, pop two elements // from stack apply the operator else { int val1 = stack.Pop(); int val2 = stack.Pop(); switch (c) { case '+' : stack.Push(val2 + val1); break ; case '-' : stack.Push(val2 - val1); break ; case '/' : stack.Push(val2 / val1); break ; case '*' : stack.Push(val2 * val1); break ; } } } return stack.Pop(); }// Driver Code public static void Main( string [] args) { string exp = "100 200 + 2 / 5 * 7 +" ; Console.WriteLine(evaluatePostfix(exp)); } }// This code is contributed by Shrikant13

python

# Python program to evaluate value of a postfix # expression with integers containing multiple digitsclass evalpostfix: def __init__( self ): self .stack = [] self .top = - 1 def pop( self ): if self .top = = - 1 : return else : self .top - = 1 return self .stack.pop() def push( self , i): self .top + = 1 self .stack.append(i)def centralfunc( self , ab): for i in ab:# if the component of the list is an integer try : self .push( int (i)) # if the component of the list is not an integer, # it must be an operator. Using ValueError, we can # evaluate components of the list other than type int except ValueError: val1 = self .pop() val2 = self .pop()# switch statement to perform operation switcher = { '+' :val2 + val1, '-' :val2 - val1, '*' :val2 * val1, '/' :val2 / val1, '^' :val2 * * val1} self .push(switcher.get(i)) return int ( self .pop())str = '100 200 + 2 / 5 * 7 +'# splitting the given string to obtain # integers and operators into a list strconv = str .split( ' ' ) obj = evalpostfix() print (obj.centralfunc(strconv))# This code is contributed by Amarnath Reddy

输出：

757

【栈用法（后缀表达式的求值）】参考文献：
http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial2.pdf
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  汽车积碳是什么意思
• 

  redis多节点同步
• 

  27岁有稳定工作,想用20万存款当做第二职业来投资,投资什么好呢？
• 

  上海戏剧学院分数线 2019年上海戏剧学院分数线
• 

  去加拿大必买清单 去加拿大买什么最划算
• 

  室内阳台养什么花最好 室内阳台适合养什么花好
• 

  火理财什么时间可以申请债权转让？债权转让收费吗
• 

  塑料菜板发黑怎么办
• 

  癌细胞|癌细胞已经转移，为什么人的精神依旧很好，而且很能吃？是好事？
• 

  详细步骤及注意事项 g2810加墨水后如何操作
• 

  佳能相机7100 佳能7100单反
• 

  有什么好看的书推荐？
• 

  你喜欢看军事小说吗？
• 

  空气阻尼器时间继电器 空气阻尼器结构图
• 

  2023春节坐高铁需要全程戴口罩吗 2021春节能坐高铁吗
• 

  台高官被问“你有接受过性招待吗
• 

  农村籍独生子女补贴如何领取？四类人无法领取有你吗？
• 

  甲氰菊酯有效是多久 甲氰菊酯药效是几天，水里多久失效
• 

  c语言连接数据库函数 c语言数据库连接池
• 

  有宠app怎么关闭资讯推送通知？有宠app关闭资讯推送通知的方法

• Go中的switch语句用法指南
• HTML页面布局代码示例
• Python程序在列表中查找最大的数字
• 如何使用PHP在网络浏览器中打开PDF文件（）
• bell数（对集合进行分区的方式数量）
• Python中的双端队列详解
• Golang指向指针的指针（双指针）介绍
• Perl中的软件包详细指南
• DetailView –基于类的视图Django