در این مطلب، برنامه ارزیابی عبارت ارائه شده است. فرض می‌شود یک رشته به کاربر داده شده است که بیان‌گر عبارتی شامل ارقام و عمل‌گرها است. برای مثال، عبارت‌های ۳*۲+۱ و ۴+۲-۱ را می‌توان در گرفت. اکنون، نیاز به ارزیابی رشته یا عبارت است. هیچ علامت‌گذاری با استفاده از پرانتز و کروشه انجام نشده است. هدف آن است که در صورت اشتباه بودن نحو عبارت، -۱ بازگردانده شود.

بررسی موردی:

مقدار ۳*۲+۱ برابر با ۹ ارزیابی می‌شود. (معتبر)

۳*۴-۲+۶ برابر با ۲۴ ارزیابی می‌شود. (معتبر)

۲++۱ برابر با -۱ ارزیابی می‌شود (نامعتبر)

همچنین، فضاهای خالی نیز ممکن است در عبارات وجود داشته باشند. در چنین شرایطی، نیاز به چشم‌پوشی از فضاهای خالی است. مثلا: ۱-۲*۱- برابر با ۱ است. این مساله، از جمله پرسش‌های مصاحبه‌های استخدامی آمازون است. راه حل این مساله ساده است. کافی است که از اولین کاراکتر کار را آغاز کرد، پیمایش را از چپ به راست انجام داد و خطاهایی مانند دو عملگر یا عمل‌وند پشت سر هم را شناسایی کرد. همچنین، می‌توان نتایج را ضمن پیمایش عبارت، پیدا کرد. در ادامه، برنامه‌ای برای ارزیابی عبارت ورودی، ارائه شده است.

برنامه ارزیابی عبارت در ++C

// C++ program to evaluate a given expression 
#include <iostream> 
using namespace std; 
  
// A utility function to check if a given character is operand 
bool isOperand(char c) { return (c >= '0' && c <= '9'); } 
  
// utility function to find value of and operand 
int value(char c) {  return (c - '0'); } 
  
// This function evaluates simple expressions. It returns -1 if the 
// given expression is invalid. 
int evaluate(char *exp) 
{ 
    // Base Case: Given expression is empty 
    if (*exp == '\0')  return -1; 
  
    // The first character must be an operand, find its value 
    int res = value(exp[0]); 
  
    // Traverse the remaining characters in pairs 
    for (int i = 1; exp[i]; i += 2) 
    { 
        // The next character must be an operator, and 
        // next to next an operand 
        char opr = exp[i], opd = exp[i+1]; 
  
        // If next to next character is not an operand 
        if (!isOperand(opd))  return -1; 
  
        // Update result according to the operator 
        if (opr == '+')       res += value(opd); 
        else if (opr == '-')  res -= value(opd); 
        else if (opr == '*')  res *= value(opd); 
        else if (opr == '/')  res /= value(opd); 
  
        // If not a valid operator 
        else                  return -1; 
    } 
    return res; 
} 
  
// Driver program to test above function 
int main() 
{ 
    char expr1[] = "1+2*5+3"; 
    int res = evaluate(expr1); 
    (res == -1)? cout << expr1 << " is " << "Invalid\n": 
                 cout << "Value of " << expr1 << " is " << res << endl; 
  
    char expr2[] = "1+2*3"; 
    res = evaluate(expr2); 
    (res == -1)? cout << expr2 << " is " << "Invalid\n": 
                 cout << "Value of " << expr2 << " is " << res << endl; 
  
    char expr3[] = "4-2+6*3"; 
    res = evaluate(expr3); 
    (res == -1)? cout << expr3 << " is " << "Invalid\n": 
                 cout << "Value of " << expr3 << " is " << res << endl; 
  
    char expr4[] = "1++2"; 
    res = evaluate(expr4); 
    (res == -1)? cout << expr4 << " is " << "Invalid\n": 
                 cout << "Value of " << expr4 << " is " << res << endl; 
    return 0; 
}

برنامه ارزیابی عبارت در جاوا

// Java program to evaluate a given expression  
  
class GFG{ 
// A utility function to check if  
// a given character is operand  
static boolean isOperand(char c)  
{  
    return (c >= '0' && c <= '9');  
      
}  
  
// utility function to find value of and operand  
static int value(char c) 
{  
    return (int)(c - '0'); 
      
}  
  
// This function evaluates simple expressions.  
// It returns -1 if the given  
// expression is invalid.  
static int evaluate(String exp)  
{  
    // Base Case: Given expression is empty  
    if (exp.length() == 0) return -1;  
  
    // The first character must be  
    // an operand, find its value  
    int res = value(exp.charAt(0));  
  
    // Traverse the remaining characters in pairs  
    for (int i = 1; i<exp.length(); i += 2)  
    {  
        // The next character must be an operator, and  
        // next to next an operand  
        char opr = exp.charAt(i), opd = exp.charAt(i+1);  
  
        // If next to next character is not an operand  
        if (isOperand(opd) == false) return -1;  
  
        // Update result according to the operator  
        if (opr == '+') res += value(opd);  
        else if (opr == '-') res -= value(opd);  
        else if (opr == '*') res *= value(opd);  
        else if (opr == '/') res /= value(opd);  
  
        // If not a valid operator  
        else                 return -1;  
    }  
    return res;  
}  
  
// Driver program to test above function  
public static void main(String[] args)  
{  
    String expr1 = "1+2*5+3";  
    int res = evaluate(expr1);  
    if(res == -1) System.out.println(expr1+" is Invalid");  
    else     System.out.println("Value of "+expr1+" is "+res);  
  
    String expr2 = "1+2*3";  
    res = evaluate(expr2);  
    if(res == -1) System.out.println(expr2+" is Invalid");  
    else         System.out.println("Value of "+expr2+" is "+res); 
  
    String expr3 = "4-2+6*3";  
    res = evaluate(expr3);  
    if(res == -1) System.out.println(expr3+" is Invalid");  
    else         System.out.println("Value of "+expr3+" is "+res); 
  
    String expr4 = "1++2";  
    res = evaluate(expr4);  
    if(res == -1) System.out.println(expr4+" is Invalid");  
    else         System.out.println("Value of "+expr4+" is "+res); 
}  
} 
// This code is contributed by mits

برنامه ارزیابی عبارت در پایتون ۳

# Python3 program to evaluate a 
# given expression 
  
# A utility function to check if 
# a given character is operand 
def isOperand(c):  
   
    return (c >= '0' and c <= '9');  
  
# utility function to find 
# value of and operand 
def value(c):  
    return ord(c) - ord('0');  
  
# This function evaluates simple 
# expressions. It returns -1 if the 
# given expression is invalid. 
def evaluate(exp): 
  
    len1 = len(exp); 
      
    # Base Case: Given expression is empty 
    if (len1 == 0): 
        return -1; 
  
    # The first character must be  
    # an operand, find its value 
    res = value(exp[0]); 
  
    # Traverse the remaining 
    # characters in pairs 
    for i in range(1,len1,2): 
        # The next character must be  
        # an operator, and next to  
        # next an operand 
        opr = exp[i]; 
        opd = exp[i + 1]; 
  
        # If next to next character  
        # is not an operand 
        if (isOperand(opd)==False): 
            return -1; 
  
        # Update result according  
        # to the operator 
        if (opr == '+'): 
            res += value(opd); 
        elif (opr == '-'): 
            res -= int(value(opd)); 
        elif (opr == '*'): 
            res *= int(value(opd)); 
        elif (opr == '/'): 
            res /= int(value(opd)); 
  
        # If not a valid operator 
        else: 
            return -1; 
      
    return res; 
  
# Driver Code 
expr1 = "1+2*5+3"; 
res = evaluate(expr1); 
print(expr1,"is Invalid") if (res == -1) else print("Value of",expr1,"is",res); 
  
expr2 = "1+2*3"; 
res = evaluate(expr2); 
print(expr2,"is Invalid") if (res == -1) else print("Value of",expr2,"is",res); 
  
expr3 = "4-2+6*3"; 
res = evaluate(expr3); 
print(expr3,"is Invalid") if (res == -1) else print("Value of",expr3,"is",res); 
  
expr4 = "1++2"; 
res = evaluate(expr4); 
print(expr4,"is Invalid") if (res == -1) else print("Value of",expr4,"is",res); 
  
# This code is contributed by mits

برنامه ارزیابی عبارت در #C

// C# program to evaluate a given expression  
using System; 
class GFG{ 
      
// A utility function to check if 
// a given character is operand  
static bool isOperand(char c) {  
    return (c >= '0' && c <= '9');  
      
}  
  
// utility function to find value of and operand  
static int value(char c) { return (int)(c - '0'); }  
  
// This function evaluates simple  
// expressions. It returns -1 if the  
// given expression is invalid.  
static int evaluate(string exp)  
{  
    // Base Case: Given expression is empty  
    if (exp.Length == 0) return -1;  
  
    // The first character must be 
    // an operand, find its value  
    int res = value(exp[0]);  
  
    // Traverse the remaining characters in pairs  
    for (int i = 1; i<exp.Length; i += 2)  
    {  
        // The next character must be an operator, and  
        // next to next an operand  
        char opr = exp[i], opd = exp[i+1];  
  
        // If next to next character is not an operand  
        if (isOperand(opd)==false) return -1;  
  
        // Update result according to the operator  
        if (opr == '+') res += value(opd);  
        else if (opr == '-') res -= value(opd);  
        else if (opr == '*') res *= value(opd);  
        else if (opr == '/') res /= value(opd);  
  
        // If not a valid operator  
        else                 return -1;  
    }  
    return res;  
}  
  
// Driver program to test above function  
static void Main()  
{  
    string expr1 = "1+2*5+3";  
    int res = evaluate(expr1);  
    if(res == -1)  
    Console.WriteLine(expr1+" is Invalid");  
    else     
    Console.WriteLine("Value of "+expr1+" is "+res);  
  
    string expr2 = "1+2*3";  
    res = evaluate(expr2);  
    if(res == -1)  
    Console.WriteLine(expr2+" is Invalid");  
    else         
    Console.WriteLine("Value of "+expr2+" is "+res); 
  
    string expr3 = "4-2+6*3";  
    res = evaluate(expr3);  
    if(res == -1)  
    Console.WriteLine(expr3+" is Invalid");  
    else         
    Console.WriteLine("Value of "+expr3+" is "+res); 
  
    string expr4 = "1++2";  
    res = evaluate(expr4);  
    if(res == -1)  
    Console.WriteLine(expr4+" is Invalid");  
    else         
    Console.WriteLine("Value of "+expr4+" is "+res); 
}  
} 
// This code is contributed by mits

برنامه ارزیابی عبارت در PHP

<?php 
// PHP program to evaluate a 
// given expression 
  
// A utility function to check if 
// a given character is operand 
function isOperand($c)  
{  
    return ($c >= '0' && $c <= '9');  
} 
  
// utility function to find 
// value of and operand 
function value($c)  
{  
    return ($c - '0');  
} 
  
// This function evaluates simple 
// expressions. It returns -1 if the 
// given expression is invalid. 
function evaluate($exp) 
{ 
    $len = strlen($exp); 
      
    // Base Case: Given expression is empty 
    if ($len == 0) return -1; 
  
    // The first character must be  
    // an operand, find its value 
    $res = (int)(value($exp[0])); 
  
    // Traverse the remaining 
    // characters in pairs 
    for ($i = 1; $i < $len; $i += 2) 
    { 
        // The next character must be   
        // an operator, and next to  
        // next an operand 
        $opr = $exp[$i]; 
        $opd = $exp[$i + 1]; 
  
        // If next to next character  
        // is not an operand 
        if (!isOperand($opd))  
        return -1; 
  
        // Update result according  
        // to the operator 
        if ($opr == '+')      
        $res += value($opd); 
        else if ($opr == '-')  
            $res -= (int)(value($opd)); 
        else if ($opr == '*')  
            $res *= (int)(value($opd)); 
        else if ($opr == '/')  
            $res /= (int)(value($opd)); 
  
        // If not a valid operator 
        else                
        return -1; 
    } 
    return $res; 
} 
  
// Driver Code 
$expr1 = "1+2*5+3"; 
$res = evaluate($expr1); 
($res == -1) ? print($expr1." is Invalid\n"): 
               print("Value of " . $expr1 .  
                     " is " . $res . "\n"); 
              
$expr2 = "1+2*3"; 
$res = evaluate($expr2); 
($res == -1) ? print($expr2." is Invalid\n"): 
               print("Value of " . $expr2 .  
                     " is " . $res . "\n"); 
              
$expr3 = "4-2+6*3"; 
$res = evaluate($expr3); 
($res == -1) ? print($expr3." is Invalid\n"): 
               print("Value of " . $expr3 .  
                     " is " . $res . "\n"); 
              
$expr4 = "1++2"; 
$res = evaluate($expr4); 
($res == -1) ? print($expr4." is Invalid\n"): 
               print("Value of " . $expr4 . 
                     " is " . $res . "\n"); 
  
// This code is contributed by mits 
?>

خروجی قطعه کد بالا به صورت زیر است.

Value of 1+2*5+3 is 18
Value of 1+2*3 is 9
Value of 4-2+6*3 is 24
۱++۲ is Invalid

کد بالا، فضاهای خالی را مدیریت نمی‌کند. می‌توان فضاهای خالی را با حذف اولیه همه فضاهای خالی از رشته داده شده، مدیریت کرد. یک راهکار بهتر، مدیریت فضاها در یک پیمایش است. مخاطبان می‌توانند این مورد را به عنوان یک تمرین انجام دهند. پیچیدگی زمانی این راهکار از درجهO(n) ‎ است که در آن، n طول عبارت ورودی است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
• برنامه تشخیص وجود دور در گراف جهت‌دار — راهنمای کاربردی
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده

منبع [+]