本文概述
后缀表示法用于表示代数表达式。与后缀形式相比, 以后缀形式编写的表达式的求值速度更快后缀不需要括号中的括号表示法。我们已经讨论过后缀到后缀的转换。在这篇文章中, 讨论了后缀表达式的评估。
以下是评估后缀表达式的算法。
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 expression
import 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 Ghoshpython
# 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 value
public 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 rathbhupendraC
// 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 KunduJava
// 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 KunduC#
// 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 Shrikant13python
# Python program to evaluate value of a postfix
# expression with integers containing multiple digits
class 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
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
