题解 | #计算表达式#

不清不楚的一题，根本没说明白条件，怪不得通过率这么低。我来补充一下这题的说明：

• 表达式中的运算符都是二元运算符，不需要处理“取负”这样的单元运算符
• 操作符只有加减乘除
• 表达式中的部分运算结果可能是非整形
• 输出是整形

由于表达式中只有两个优先级的操作符，于是该表达式的求值可以化为一趟扫描和一趟相加：

1. 第一趟扫描表达式，顺便把高优先级的运算做了，把数字和低优先级符号分别存储在两个向量中。
2. 第二趟把低优先级的运算算完。注意要保持左结合，减法对减法、加法都不满足结合律。

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>

using namespace std;

int evaluate(const string &expression)
{
  vector<double> terms;
  vector<char> ops;
  string rest = expression;
  while (rest.length() != 0)
  {
    if (isdigit(rest[0])) {
      size_t size;
      auto a = stod(rest, &size);
      rest = rest.substr(size);

      if (ops.size())
      {
        auto left = terms.back();
        switch (ops.back())
        {
        case '*':
          terms.pop_back();
          terms.push_back(left * a);
          ops.pop_back();
          break;
        case '/':
          terms.pop_back();
          terms.push_back(left / a);
          ops.pop_back();
          break;
        case '+':
        case '-':
          terms.push_back(a);
          break;
        default:
          std::cout << "[err]: " << __LINE__ << endl;
          break;
        }
      } else {
        terms.push_back(a);
      }
    } else {
      ops.push_back(rest[0]);
      rest = rest.substr(1);
    }

    /* || For Debugging */
    // std::cout << "terms: ";
    // for (auto t : terms)
    // {
    //   std::cout << t << ' ';
    // }
    // std::cout << endl;

    // std::cout << "ops: ";
    // for (auto op : ops)
    // {
    //   std::cout << op << ' ';
    // }
    // std::cout << endl;
    // std::cout << "Rest: " << rest << '\n' << endl;
  }

  reverse(terms.begin(), terms.end());

  for (auto it = ops.begin(); it != ops.end(); it++)
  {
    // the terms has reverse order
    auto left = terms.back();
    terms.pop_back();
    auto right = terms.back();
    terms.pop_back();
    switch (*it)
    {
    case '+':
      terms.push_back(left + right);
      break;
    case '-':
      terms.push_back(left - right);
      break;
    default:
      std::cout << "[err]: " << __LINE__ << endl;
    }
  }

  if (terms.size() != 1)
  {
    std::cout << "[err]: " << __LINE__ << endl;
  }

  return terms[0];
}

int main()
{
  string expression;
  cin >> expression;
  auto value = evaluate(expression);
  std::cout << value << endl;
}