本文概述

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

推荐阅读

• 

  盐水加白醋泡脚的好处 舒服每一晚
• 

  床单起球是质量问题吗
• 

  马上消费金融额度是多少
• 

  上环后图片 避孕环是什么样子图片
• 

  SpringBoot配置并使用Redis缓存服务
• 

  1秒钟等于几毫秒 一秒等于多少毫秒多少微秒
• 

  罗汉松有哪些品种如何区分
• 

  中年之殇
• 

  电脑里编程的软件有哪些，目前计算机编程的常用软件有什么
• 

  网易怒斥暴雪:离婚不离身 暴雪是不是网易的
• 

  cfree里面怎么一步一步分析结果
• 

  山东良法领导干部知识竞赛题目是什么？领导干部知识题库大全
• 

  95和98的暗语是什么意思 98是什么
• 

  vxlan 格式 分析
• 

  如何在手机上连接黑魂2服务器？ 黑魂2服务器怎么用手机
• 

  医生竟会对孕检女子做出这事，女子怀孕去医院检查
• 

  崩坏3新版本新增内容汇总 3.4版本相关调整内容前瞻
• 

  中国民俗的“鬼节”有哪些？中元节和清明节有什么区分？
• 

  张裕干红葡萄酒口感怎么样 张裕特选级干红葡萄酒怎么样
• 

  看财报|苏酒老二今世缘百亿冲刺第一战：7%的省外营收如何撬动全国化市场？｜ 看财报

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