现在的位置: 首页 > 综合 > 正文

一个简单的表达式计算器的C++实现

2013年10月12日 ⁄ 综合 ⁄ 共 8529字 ⁄ 字号 小 中 大 ⁄ 评论关闭

这个程序的编写本质上主要是栈的应用。我的程序主要分为2部分。第一部分为把输入的中缀表达式转换为后缀表达式，第二部分为计算后缀表达式。2个部分都用一个栈来辅助操作并检查表达式的是否合法。

（1）、中缀表达式转换为后缀表达式：

函数int infix_to_postfix(const string& infix, string& postfix);执行中缀表达式转换为后缀表达式的计算。它使用一个栈来存储遇到的操作符和左括号，遇到操作数则直接输出。

操作符在入栈的时候要比较栈顶符号和待入栈符号的优先级，优先级高的操作符意味着它要先计算，所以要先输出。

当优先级相同时，（a）如果是待入栈操作符是左结合性，则先输出栈顶的那个操作符，这样直到栈顶符号的优先级小于当前待入栈的符号为止。然后把待入栈的操作符压入栈中；（b）如果待入栈操作符是右结合性，则要把操作符直接入栈。比如在本程序中，我们对^预算符就是这么处理的。

在转换过程中，还有一个比较特殊的符号，那就是括号。括号在中缀表达式中是用来确定计算先后顺序的，但是在后缀表达式中，它就不再需要了。计算的顺序是通过后缀表达式的性质来保证的。把一对括号中的中缀表达式转换为后缀表达式，然后把括号直接去掉就可以了。所以对括号的处理就是：遇到左括号，和其他的运算符一样，把比它优先级还要高的运算符弹出来（但是遇到左括号时就要停止了），然后把左括号入栈。遇到右括号时，则出栈，即把一对括号之间的中缀表达式已经转为后缀表达式了。当左括号为栈顶的时候，停止出栈循环，然后弹出栈顶的左括号。

 

（2）计算后缀表达式：

       int compute_postfix(const string& postfix_expr, double& result);用来计算前面产生的后缀表达式。这个过程比较简单，遇到操作数时，直接入栈；由于在后缀表达式中，操作符都是在它的操作数后面的，所以遇到操作符时，就从栈中取出这个操作符需要的操作数然，进行必要的检查后，就可以进行计算了。计算结果再次压入栈中，供后面使用。当后缀表达式处理完毕后，最后的结果就是栈顶了。

 

上面介绍的两个部分都用到了int getToken(const string& expr, string& token, size_t& idx);函数。这个函数的作用是：把输入的表达式切分为一个个的操作符或者操作数，供使用。

 

代码如下：

 

  1. #define _CRT_SECURE_NO_WARNINGS // for MS crt.
  3. #include <fstream>
  4. #include <stack>
  5. #include <string>
  6. #include <iomanip>
  7. #include <cmath>
  8. using namespace std;
  10. bool isLetter(char c);
  11. bool isOperator(char c);
  12. bool isBracket(char c);
  13. int getToken(const string& expr, string& token, size_t& idx);
  14. int getOperatorPriority(const string& op);
  15. int infix_to_postfix(const string& infix, string& postfix);
  16. int compute_postfix(const string& postfix_expr, double& result);
  18. int main()
  19. {
  20.     ifstream cin("input.txt");          // input
  21.     ofstream cout("output.txt");        // output
  22.     string infix_expr, postfix_expr;
  23.     double result = 0.0;
  24.     
  25.     while (getline(cin, infix_expr)) {
  26.         if (infix_to_postfix(infix_expr, postfix_expr)) {
  27.             if (compute_postfix(postfix_expr, result)) {
  28.                 cout << fixed << setprecision(2) << result << endl;
  29.                 continue ; // have no error, so next expr.
  30.             }
  31.         }
  32.     
  33.         cout << "ERROR IN INFIX NOTATION" << endl;
  34.     }
  35.     return 0;
  36. }
  38. int infix_to_postfix(const string& infix_expr, string& postfix_expr)
  39. {
  40.     string token;
  41.     size_t idx = 0;
  42.     stack<string> stk;
  43.     int balance = 0; // use to check the bracket's balance.
  45.     postfix_expr.clear();
  46.     while (getToken(infix_expr, token, idx)) {
  47.         switch (token[0]) {
  48.             /* If we see '+','-','*','/','%','^','(' , then we pop entries from
  49.              * the stack until we find an entry of lower priority
  50.              * One exception is that we never remove a '(' from the stack except when processing a ')'.*/
  51.             case '+':
  52.             case '-':
  53.             case '*':
  54.             case '/':
  55.             case '%':
  56.             case '(':
  57.                 if (token[0] == '(')
  58.                     ++balance;
  59.                 while (!stk.empty() && getOperatorPriority(stk.top()) >= getOperatorPriority(token) && stk.top() != "(") {
  60.                     postfix_expr += stk.top();
  61.                     stk.pop();
  62.                     postfix_expr += " ";
  63.                 }
  64.                 stk.push(token);
  65.                 break;
  66.             /* right association, handle it specifically! */
  67.             case '^':
  68.                 while (!stk.empty() && getOperatorPriority(stk.top()) > getOperatorPriority(token) && stk.top() != "(") {
  69.                     postfix_expr += stk.top();
  70.                     stk.pop();
  71.                     postfix_expr += " ";
  72.                 }
  73.                 stk.push(token); // later come, early out.(right association)
  74.                 break;
  75.             /* If we see a ')', then we pop the stack, writing symbols until we encounter
  76.              * a (corresponding) left parenthesis, which is poped but not output. */
  77.             case ')':
  78.                 --balance;
  79.                 while (!stk.empty() && stk.top() != "(") {
  80.                     postfix_expr += stk.top();
  81.                     stk.pop();
  82.                     postfix_expr += " ";
  83.                 }
  84.                 stk.pop();
  85.                 break;
  86.             default:
  87.                 postfix_expr += token;
  88.                 postfix_expr += " ";
  89.                 break;
  90.         }
  91.     }
  92.     while (!stk.empty()) {
  93.         postfix_expr += " ";
  94.         postfix_expr += stk.top();
  95.         stk.pop();
  96.     }
  97.     if (balance != 0) {
  98.         return 0;
  99.     }
  101.     return 1;
  102. }
  104. int compute_postfix(const string& postfix_expr, double& result)
  105. {
  106.     stack<string> stk;
  107.     string token;
  108.     size_t idx = 0;
  109.     double operand1 = 0.0, operand2 = 0.0;
  110.     char buf[128] = {0};
  111.     int resStatus = 0;
  113.     while (getToken(postfix_expr, token, idx)) {
  114.         memset(buf, 0, 128 * sizeof(char));
  115.         switch (token[0]) {
  116.             case '+':
  117.             case '-':
  118.             case '*':
  119.             case '/':
  120.             case '%':
  121.             case '^':
  122.                 // firstly, get two operands to compute.
  123.                 operand1 = atof(stk.top().c_str());
  124.                 stk.pop();
  125.                 operand2 = atof(stk.top().c_str());
  126.                 stk.pop();
  127.                 switch (token[0]) {
  128.                     case '+':
  129.                         sprintf(buf, "%f", operand1 + operand2);
  130.                         break;
  131.                     case '-':
  132.                         sprintf(buf, "%f", operand2 - operand1);
  133.                         break;
  134.                     case '*':
  135.                         sprintf(buf, "%f", operand1 * operand2);
  136.                         break;
  137.                     case '/':
  138.                         if (!operand1) {
  139.                             resStatus = 0;
  140.                             goto Exit;
  141.                         }
  142.                         sprintf(buf, "%f", operand2 / operand1);
  143.                         break;
  144.                     case '%':
  145.                         // if operand is a float number, then error!
  146.                         if ((int)operand1 != operand1 || (int)operand2 != operand2 || !operand1) {
  147.                             resStatus = 0;
  148.                             goto Exit;
  149.                         }
  150.                         // care: the format should be "%d".
  151.                         sprintf(buf, "%d", (int)operand2 % (int)operand1);
  152.                         break;
  153.                     case '^':
  154.                         if (operand2 <= 0) {
  155.                             resStatus = 0;
  156.                             goto Exit;                      
  157.                         }
  158.                         sprintf(buf, "%f", pow(operand2, operand1));
  159.                         break;
  160.                 }
  161.                 stk.push(string(buf)); 
  162.                 break;
  163.             default:
  164.                 stk.push(token); // numbers push into the stack directly.
  165.                 break;
  166.         }
  167.     }
  168.     // now the number in the stack is the result.
  169.     result = atof(stk.top().c_str());
  170.     resStatus = 1;
  172. Exit:
  173.     return resStatus;
  174. }
  176. int getOperatorPriority(const string& op)
  177. {
  178.     int priority = -1;
  180.     switch (op[0])
  181.     {
  182.         case '(':
  183.             priority = 4;
  184.             break;
  185.         case '+':
  186.         case '-':
  187.             priority = 1;
  188.             break;
  189.         case '*':
  190.         case '/':
  191.         case '%':
  192.             priority = 2;
  193.             break;
  194.         case '^':
  195.             priority = 3;
  196.             break;
  197.     }
  199.     return priority;
  200. }
  202. int getToken(const string& expr, string& token, size_t& idx)
  203. {
  204.     char curChar = 0;
  205.     bool inTok = false ;
  206.     int res = 0;
  208.     token.clear();
  209.     size_t len = expr.length();
  210.     while (idx < len) {
  211.         curChar = expr[idx++];
  212.         if (isspace(curChar) || isOperator(curChar) || isBracket(curChar)) {
  213.             if (!inTok && (isOperator(curChar) || isBracket(curChar))) {
  214.                 token += curChar;
  215.                 res = 1; // token is a operatro or bracket, return token immediately.
  216.                 break;
  217.             }
  218.             if (inTok) {
  219.                 if (isOperator(curChar) || isBracket(curChar))
  220.                     --idx; // back input pointer and get the operator or bracket when we call getToken() next time.
  221.                 res = 1;
  222.                 break;
  223.             }
  224.             inTok = false;
  225.         }  else if (isLetter(curChar)) { // letter is illegal.
  226.             res = 0;
  227.             break;
  228.         }  else if (!inTok) { // begin a number.
  229.             inTok = true;
  230.             token += curChar;
  231.         } else if (inTok) {
  232.             token += curChar;
  233.         }
  234.     }
  235.     if (!token.empty())
  236.         res = 1;
  238.     return res;
  239. }
  241. bool isLetter(char c)
  242. {
  243.     if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
  244.         return true;
  245.     return false;
  246. }
  248. bool isOperator(char c)
  249. {
  250.     if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^')
  251.         return true ;
  252.     return false ;
  253. }
  255. bool isBracket(char c)
  256. {
  257.     if (c == '(' || c == ')')
  258.         return true;
  259.     return false;
  260. }

 

 

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞