首页 > 代码库 > 算法学习记录-栈的应用--表达式运算

算法学习记录-栈的应用--表达式运算

前面做了栈的基本操作

总感觉需要做一个实际的例子来检验一下。

这里我将用栈来做一个简单的四则运算。

目标比较简单:

做一个带小括号(“()”)的四则运算,如果要加入到中括号(“[]”)或者大括号(“{}”),依次类推。

求一个表达式:

用下面这个算是做例子,程序最后应该可以算出任何带小括号的运算。

3+(32-6)*9+5*3-(3*(65-15)/5)+12;

 

方法一:后缀法。

1.了解中缀和后缀表示法

中缀表示法:刚才的那个算是就是中缀表示法,我们通常看到的数学符号就是中缀表示法,即数字在计算符号的两边。

后缀表示法:所有的计算符号在数字之后。不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行。

原理:从左到右遍历表达式,如果是数字则输出,如果是符号:判断该符号与栈顶的符号优先级,

    如果是右括号或者优先级低于栈顶符号,则栈中元素依次出栈并输出,并且将当前符号进栈。

 

对上面的式子进行处理:

 

后序表达式用处

当转换成后序表达式后更方便计算表达式的值,如将后序表达式的元素依次进栈直到遇到运算符,这时候从栈中弹出两个元素,再结合运算符计算出这两个数运算的结果(如6-9=3),将其结果压栈(此时栈元素为3 23 -3),然后继续将后序非符号元素压栈,直到遇到运算符。重复之前的操作。。。

InfixExp(中序表达式)转换PostfixExp(后序表达式)算法

1)当输入的是操作数时候,直接输出到后序表达式PostfixExp序列中

2)当输入开括号时候,把它压栈

3)当输入的是闭括号时候,先判断栈是否为空,若为空,则发生错误并进行相关处理。若非空,把栈中元素依次弹出并输出到Postfix中,知道遇到第一个开括号,若没有遇到开括号,也发生错误,进行相关处理

4)当输入是运算符op(+、- 、×、/)时候

a)循环,当(栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级)时,反复操作:将栈顶元素弹出并添加到Postfix中

b)把输入的运算符op压栈

5)当中序表达式InfixExp的符号序列全部读入后,若栈内扔有元素,把他们依次弹出并放到后序表达式PostfixExp序列尾部。若弹出的元素遇到空括号,则说明不匹配,发生错误,并进行相关处理

 

编写了一个程序如下: 比较烂

  1 #include <iostream>  2 #include <string>  3 #include <vector>  4 #include <stack>  5   6 using namespace std;  7   8 int get_proi(char ch)  9 { 10     switch(ch) 11     { 12     case +: 13     case -:return 1; 14  15     case *: 16     case /:return 2; 17  18     case (: 19     case ):return 3; 20     } 21 } 22  23 void predo(string &str) 24 { 25     string ot; 26     int k=0; 27     for (int i=0;i<str.size();i++) 28     { 29         if (isdigit(str[i]) || isspace(str[i]) ||  30             str[i] == + || str[i] == - || str[i] == * || str[i] == / || 31             str[i] == ( || str[i] == )) 32         { 33             ot.push_back(str[i]); 34         } 35     } 36     str = ot; 37 } 38  39 bool in_to_pre(string &str,vector<string> &vec)//中序-->后序 40 { 41     vector<string> dest; 42     stack<string> opstack; 43     bool flag = false; 44     int k=0; 45     int i=0; 46     //get every elem 47     while(i<str.size()) 48     { 49         i=k; 50         string elem; 51         if (isdigit(str[i])) 52         { 53             while(i<str.size() && isdigit(str[i])) 54             { 55                 elem.push_back(str[i]); 56                 i++; 57             } 58             k = i; 59             vec.push_back(elem); 60         } 61         else if (str[i] == + || str[i] == - || str[i] == * || str[i] == / || str[i] == ( || str[i] == )) 62         { 63             elem.push_back(str[i]); 64             vec.push_back(elem); 65             i++; 66             k = i; 67         } 68     } 69     // in to pre 70     int deep = 0; 71     for (vector<string>::iterator it = vec.begin();it!=vec.end();it++) 72     { 73         string tmp = *it; 74          75         if (isdigit(tmp[0])) 76         {//1如果是数字直接放入dest中 77             dest.push_back(tmp); 78         } 79         else 80         {//2如果是操作符则需要判断 81             //2.1.如果是 “(”,压栈op 82             if (tmp[0] == () 83             { 84                 opstack.push(tmp); 85                 deep++; 86             } 87             //2.2.如果是 “)”,出栈直到“(” 88             else if (tmp[0] == )) 89             { 90                 while(!opstack.empty() && opstack.top().at(0) != () 91                 { 92                     dest.push_back(opstack.top()); 93                     opstack.pop(); 94                 } 95                 if (opstack.empty()) 96                 { 97                     return -1; 98                 } 99                 else 100                 {101                     deep--;102                     opstack.pop();103                 }104             }105             //3.不是括号106             //3.1 循环,当(栈非空 and 栈顶不是开括号 and 栈顶运算符的优先级 不低于 输入的运算符的优先级)时,反复操作:将栈顶元素退出压入后序栈中107             else if (!opstack.empty() && opstack.top().at(0) != ( && get_proi(opstack.top().at(0)) >= get_proi(tmp[0]))108             {109                 while(!opstack.empty() && opstack.top().at(0) != ( && get_proi(opstack.top().at(0)) >= get_proi(tmp[0]))110                 {111                     dest.push_back(opstack.top());112                     opstack.pop();113                 }114                 opstack.push(tmp);115             }116             //3.2 压入 操作符 栈中117             else118             {119                 opstack.push(tmp);120             }121         }122     }123     while(!opstack.empty())124     {125         dest.push_back(opstack.top());126         opstack.pop();127     }128     if (deep != 0)129     {130         return -1;131     }132     else133     {134         vec = dest;135         return 1;136     }137 }138 139 string cacl(string str1,string str2,string op,stack<string> &opt)140 {141     char oo = op.at(0);142     double num1 = atof(str1.c_str());143     double num2 = atof(str2.c_str());144     double sum=0;145     switch(oo)146     {147     case +:sum =  num1+num2;break;148     case -:sum =  num1-num2;break;149     case *:sum =  num1*num2;break;150     case /:sum =  num1/num2;break;151     }152     153     char t[256];154     string s;155 156     sprintf(t, "%f", sum);157     s = t;158     return s;159 }160 161 void do_cacl(vector<string> &vec)162 {163     stack<string> opt;164     for (vector<string>::iterator it = vec.begin();it!=vec.end();it++)165     {166         string tmp = *it;167         if (isdigit(tmp[0]))168         {169             opt.push(tmp);170         }171         else172         {173             string str2 = opt.top();174             opt.pop();175             string str1 = opt.top();176             opt.pop();177             178             opt.push(cacl(str1,str2,tmp,opt));179         }180     }181     cout<<opt.top();182 }183 int main()184 {185     string in;186     getline(cin,in);187     predo(in);188     //not use negative189     vector<string> vecpre;190     in_to_pre(in,vecpre);191     192     do_cacl(vecpre);193 194 195     return 0;196 }
View Code

 

 

 

 

2.运算的优先级: