首页 > 代码库 > 表达式求值（只包括小括号）

表达式求值（只包括小括号）

2024-07-18 21:36:41   222人阅读

表达式求值

前缀式：就是将操作符放到数值的前面；如：a+b :  +ab；

中缀式：就是将操作符放在数值中间，其实就是我们平时生活中所写的正常的表达式。如：a+b；

后缀式：就是将操作符放在数值的后面，比如：a+b：——ab+.

对于表达式求值，最简单的当然是对后缀表达式（也称为逆波兰式）进行求值了。

而我们生活中所写的运算表达式，一般都是中缀表达式。但是我们计算的时候用到的却是后缀表达式。这就需要我们首先将中缀表达式转换为后缀表达式，然后再进行运算了。

1、中缀式转换为后缀式

下面是将中缀式（常见运算式）转换为后缀式的算法（该算法只能处理只包含“（”和“）”的运算符）：

栈底放‘#’，从左至右逐字读取中缀式：
   a.当当前字符为数字时，直接输出；
   b.当当前字符为"("时，将其压栈；
   c.当当前字符为")"时，则弹出堆栈中最上的"("之前的所有运算符并输出，然后删除堆栈中的"(" ；
   d.当当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到"("之前为止)，输出，再将当前运算符压栈；
   e.当为"#"时，弹出所有栈中的内容输出

中缀式：a*(b+c)/d+e

后缀式：abc+*d/e+

2、后缀式计算

计算后缀表达式的具体算法如下：

首先定义一个栈stk，用于存放计算结果。

　　a.当前元素为数值，直接入栈；

　　b.如果当前元素是运算符，则将stk中栈顶的两个元素弹出：m，n；

　　c.根据运算符类别（+、-、*、/）计算t = n op m;(m 是第一个弹出栈的元素)；

　　d.将计算的结果t重新压入栈stk中。

　　e.当后缀表达式还未结束，转到a继续执行，否则计算结束。stk此时的栈顶元素即是最后的计算结果。

具体的实现代码如下所示：

  1 #include <iostream>  2 #include <fstream>  3 #include <sstream>  4 #include <stack>  5 #include <vector>  6 #include <map>  7 #include <string>  8 #include <algorithm>  9 using namespace std; 10  11 map<char,int> priority; 12  13 void setPriority() 14 { 15     priority[‘-‘] = 1; 16     priority[‘+‘] = 1; 17     priority[‘*‘] = 2; 18     priority[‘/‘] = 2; 19 } 20  21 void InfixToPostfix(const string &src,vector<char> &exp) 22 { 23     int i,n; 24     stack<char> op; 25  26     n = src.size(); 27     for (i = 0; i < n; i++) 28     { 29         switch(src[i]) 30         { 31         case ‘(‘: 32             op.push(src[i]); 33             break; 34         case ‘)‘: 35             while (op.size() != 0 && op.top() != ‘(‘) 36             { 37                 exp.push_back(op.top()); 38                 op.pop(); 39             } 40             op.pop(); 41             break; 42         case ‘+‘: 43         case ‘-‘: 44         case ‘*‘: 45         case ‘/‘: 46             while (op.size() != 0 && priority[op.top()] >= priority[src[i]]) 47             { 48                 exp.push_back(op.top()); 49                 op.pop(); 50             } 51              52             op.push(src[i]); 53             break; 54         case ‘ ‘: 55             break; 56         default: 57             while (isdigit(src[i]) && i<n) 58             { 59                 exp.push_back(src[i]); 60                 i++; 61             } 62             i--; 63             exp.push_back(‘#‘); 64         } 65     } 66     while (op.size() !=0 ) 67     { 68         exp.push_back(op.top()); 69         op.pop(); 70     } 71 } 72  73 void displayExp(vector<char> &src) 74 { 75     int i,n; 76     n = src.size(); 77     for (i = 0; i < n; i++) 78     { 79         cout<<src[i]; 80     } 81     cout<<endl; 82 } 83  84 void initArray(char a[],int n) 85 { 86     int i; 87     for (i = 0; i < n; i++) 88     { 89         a[i] = ‘\0‘; 90     } 91 } 92  93 int calculate(int a,int b,char op) 94 { 95     switch (op) 96     { 97     case ‘+‘: 98         return a+b; 99         break;100     case ‘-‘:101         return a-b;102         break;103     case ‘*‘:104         return a*b;105         break;106     case ‘/‘:107         if (b != 0)108         {109             return a/b;110         }111         else112         {113             return 0;114         }115     default:116         perror("error!\n");117     }118 }119 120 int calculatePostfix(const vector<char> &src)121 {122     stack<int> stk;123     char str[10];124     int i,n,temp,k;125     int opd1,opd2;126     int result;127 128     n = src.size();129     130     for (i = 0; i < n; i++)131     {132         switch(src[i])133         {134         case ‘#‘:135             break;136         case ‘+‘:137         case ‘-‘:138         case ‘*‘:139         case ‘/‘:140             opd2 = stk.top();141             stk.pop();142             opd1 = stk.top();143             stk.pop();144             result = calculate(opd1,opd2,src[i]);145             stk.push(result);146             break;147         default:148             k = 0;149             while ((isdigit(src[i])) && (i < n))150             {151                 str[k++] = src[i++];152             }153             temp = atoi(str);154             stk.push(temp);155             initArray(str,10);156             i--;157         }158     }159     return result;160 }161 162 int main()163 {164     ifstream in("data.txt");165     string src;166     int result;167     vector<char> postfix;168     getline(in,src);169     170     setPriority();171     InfixToPostfix(src,postfix);172     displayExp(postfix);173     result = calculatePostfix(postfix);174     cout<<src<<" = "<<result;175     cout<<endl;176     return 0;177 }

 


联系
我们