本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• 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
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  博世热水器代码怎么样是什么故障,出现这故障是什么原因
• 

  vb.netdism的简单介绍
• 

  汕头好玩还是潮州好玩
• 

  清扬洗发水什么成份和功效
• 

  京东商城界面设计分析
• 

  武汉周黑鸭的做法 武汉黑鸭子
• 

  直播团单工具，主播团播有什么任务
• 

  温馨诚挚生日祝福语一句话
• 

  佳明导航仪
• 

  关于杜甫的古诗 杜甫的古诗有哪些
• 

  Spring|Spring 注解配置（2）——@Autowired
• 

  thinkphp手动记录日志，php如何记录日志
• 

  事实重婚罪公安局未立案 重婚罪公安不立案
• 

  小游戏制作平台，怎么制作微信的小游戏什么平台适合
• 

  油鱼的功效与作用
• 

  wosports S6使用说明
• 

  李银河新浪微博 李银河的博客
• 

  亮点|终于等来华为P50系列发布会 新品亮点价格全在这！
• 

  网络安全解决方案,校园网网络安全解决方案
• 

  this怎么读英语语音 this怎么读英语

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