四则运算表达式求值(栈的应用)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

1.前/中/后缀表达式的转换(首先需要明白三者之间的转换)      自然表达式转换为前/中/后缀表达式,其实是很简单的。首先将自然表达式按照优先级顺序,构造出与表达式相对应的二叉树,然后对二叉树进行前/中/后缀遍历,即得到前/中/后缀表达式。     举例说明将自然表达式转换成二叉树:     a×(b+c)-d     ① 根据表达式的优先级顺序,首先计算(b+c),形成二叉树    

tree1.JPG

       ②然后是a×(b+c),在写时注意左右的位置关系    

tree2.JPG

   ③最后在右边加上 -d    

tree3.JPG

    然后最这个构造好的二叉树进行遍历,三种遍历的顺序分别是这样的:     ① 前序遍历:根-左-右    ② 中序遍历:左-根-右    ③ 后序遍历:左-右-根     所以还是以刚才的这个例子,在最终二叉树的基础上可以得出:     前缀表达式:-*a+bcd     中缀表达式:a*b+c-d     后缀表达式:abc+*d- 2.中缀表达式转后缀表达式(栈的应用)    中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式为“9 3 1- 3 * + 10 2 / +”.

   规则:从左到右遍历中缀表达式的每一数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈  顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

    a.初始化一空栈,用来对符号进出栈使用。

    b.第一个字符是数字9,输出9,后面是符号“+”,进栈。

    c.第三个字符是“(”,依然是符号,因其只是左括号,还没有配对,故进栈。

    d.第四个字符是数字3,输出,总表达式为9 3,接着是“-”,进栈。

    e.接下来是数字1,输出,总表达式为9 3 1,后面是符号“)”,此时,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有“-”,因此输出“-”。总的表达式为9 3 1 -。

    f.接着是数字3,输出,总的表达式为9 3 1 – 3.紧接着是符号“*”,因为此时的栈顶符号为“+”号,优先级低于“*”,因此不输出,“*”进栈。

    g.之后是符号“+”,此时当前栈顶元素“*”比这个“+”的优先级高,因此栈中元素出栈并输出(没有比“+”更低的优先级,所以全部出栈),总输出表达式为9 3 1 – 3 * +。然后将当前这个符号“+”进栈。

    h.紧接着数字10,输出,总表达式为9 3 1 – 3 * + 10。后是符号“/”,所以“/”进栈。

    i.最后一个数字2,输出,总的表达式为9 3 1 – 3 * + 10 2。

    j.因已经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 – 3 * + 10 2 / +。

3.后缀表达式计算结果(栈的应用)

   后缀表达式为:9 3 1 – 3 * + 10 2 / +

   规则为:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

   a.初始化一个空栈。此栈用来对要运算的数字进行进出使用。

   b.后缀表达式中前三个是、都是数字,所以9 3 1 进栈。

   c.接下来是“-”,所以将栈中的1出栈作为减数,3出栈作为被减数,并运算3-1得到2,再讲2进栈。

   d.接着是数字3进栈。

   e.后面是“*”,也就意味着栈中3和2出栈,2与3相乘,得到6,并将6进栈。

   f.下面是“+”,所以栈中6和9出栈,9和6相加,得到15,将15进栈。

   g.接着是10和2两数字进栈。

   h.接下来是符号“/”,因此,栈顶的2与10出栈,10与2相除,得到5,将5进栈。

   i.最后一个是符号“+”,所以15与5出栈并相加,得到20,讲20进栈。

   j.结果是20出栈,栈变为空。

//下面的代码只是支持一些简单的整数的加减乘除运算,而且不支持浮点数,负数或者数字大于9的数字的运算,只是//自己简单的写一个代码,将这个过程进行的简单验证,如果需要解决复杂的计算问题,可以上网查找资料来实现! #include<iostream>#include<cstdio>#include<string>#include<stack>using namespace std; stack<char> s; stack<int> ss;  int main(){    int len1, len2, len, i, j;    string str1, str2;//str1为中缀表达式,str2为后缀表达式     while (1){          //中缀表达式转换为后缀表达式           getline(cin, str1);          len1 = str1.length();          str2.clear();           for (i = 0; i < len1; i++){              if (str1[i] >= '0' && str1[i] <= '9')                  str2.push_back(str1[i]);              else{                   if (s.size() == 0 || str1[i] == '(')                       s.push(str1[i]);                   else{                        char tmp1 = s.top();                        if (str1[i] == ')'){                            len = s.size();                            while (len){                                 char tmp = s.top();                                 s.pop();                                if (tmp == '(')                                    break;                                else                                     str2.push_back(tmp);                                 len--;                             }                         }                         else{                             if (tmp1 == '*' || tmp1 == '/'){                                 if (str1[i] == '*' || str1[i] == '/')                                      s.push(str1[i]);                                 else{                                      len = s.size();                                       while (len){                                          char tmp = s.top();                                           str2.push_back(tmp);                                          s.pop();                                           len--;                                       }                                      s.push(str1[i]);                                   }                              }                              else{                                  s.push(str1[i]);                              }                         }                    }                }           }          if (s.size() != 0){              len = s.size();               while (len){                  char tmp = s.top();                   str2.push_back(tmp);                  s.pop();                   len--;               }           }           cout << str2 << endl;          //由后缀表达式计算结果           int temp1, temp2, temp3;           len2 = str2.length();          for (i = 0; i < len2; i++){              if (str2[i] >= '0' && str2[i] <= '9'){                   int t = str2[i]-48;                   ss.push(t);               }               else{                   temp1 = ss.top();                   ss.pop();                   temp2 = ss.top();                   ss.pop();                    if (str2[i] == '+'){                       temp3 = temp2 + temp1;                    }                   else if (str2[i] == '-'){                        temp3 = temp2 - temp1;                    }                   else if (str2[i] == '*'){                        temp3 = temp2 * temp1;                    }                   else if (str2[i] == '/'){                        temp3 = temp2 / temp1;                    }                   ss.push(temp3);               }          }          cout << ss.top() << endl;     }         system("pause");}

点这里可以跳转到人工智能网站

0 0 投票数
文章评分
订阅评论
提醒
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x
()
x