本文概述

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

推荐阅读

• 

  离群点分析应用,spss离群点分析
• 

  上海招聘网站有哪些 上海招聘网站
• 

  win10电脑屏幕倒过来了解决方法
• 

  尼康AF-S DX 尼克尔 35mm f/1.8G 尼康afs1855
• 

  狗狗去抢年轻人的滑板玩，还知道助跑跳上去，这是在嘲讽人家吗？
• 

  u盘打开ghost,教您如何运用u盘打开盘自已手工ghost备份系统
• 

  减重记录2
• 

  同学生日送什么礼物好女 大学同学生日送什么礼物好女
• 

  行车记录仪怎么安装走线 行车记录仪怎么安装
• 

  iphone4|尼康衰落，iPhone背锅？
• 

  马齿苋会影响月经吗
• 

  软籽石榴吃了有什么好处
• 

  打卡Hello Kitty Sweet hellokitty主题餐厅
• 

  兴味怎么读拼音怎么写 兴味怎么读
• 

  项目无法添加tomcat，如何修改项目的jdk版本，Java version 1.8 is not supported
• 

  菲斯曼锅炉怎么测算房间面积？
• 

  wav音乐在哪下载 整轨的wav如何分割，wav整轨变分轨
• 

  小程序注册成功文案，小程序注册好了怎么开发
• 

  Flutter项目实战之Flutter_Gank
• 

  圣女果的保存方法 圣女果的保存方式

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