1918 簡單電腦

問題 A: 簡單電腦

時間限制: 1 Sec

記憶體限制: 32 MB

送出: 258

解決: 81

​​送出​​​

​​​狀态​​

題目描述

讀入一個隻包含 +, -, *, / 的非負整數計算表達式，計算該表達式的值。

輸入

測試輸入包含若幹測試用例，每個測試用例占一行，每行不超過200個字元，整數和運算符之間用一個空格分隔。沒有非法表達式。當一行中隻有0時輸入結束，相應的結果不要輸出。

輸出

對每個測試用例輸出1行，即該表達式的值，精确到小數點後2位。

樣例輸入

30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 920      

樣例輸出

#include<iostream>
#include<cstdio>
#include<string>
#include<stack>
#include<queue>
#include<map>
using namespace std;

struct node
{
  double num;//操作數
  char op;//操作符
  bool flag;//true表示操作數,false表示操作符
};

string str;
stack<node> s;//操作符棧
queue<node> q;//字尾表達式序列
map<char, int> op;
void change()//将中綴表達式轉換為字尾表達式
{
  double num;
  node temp;
  for (int i = 0; i < str.length();)
  {
    if (str[i] >= '0'&&str[i] <= '9')//如果是數字
    {
      temp.flag = true;//标記是數字數
      temp.num = str[i++] - '0';//記錄這個操作數的第一個數位
      while (i < str.length() && str[i] >= '0'&&str[i] <= '9')
      {
        temp.num = temp.num * 10 + (str[i] - '0');//更新這個操作數
        i++;
      }
      q.push(temp);//将這個操作數壓入字尾表達式的隊列
    }
    else//如果是操作符
    {
      temp.flag = false;//标記是操作符
      //隻要操作符棧的棧頂元素比該操作符優先級高
      //就把操作符棧棧頂元素彈出到字尾表達式的隊列中
      while (!s.empty() && op[str[i]] <= op[s.top().op])
      {
        q.push(s.top());
        s.pop();
      }
      temp.op = str[i];
      s.push(temp);//把該操作符壓入操作符棧中
      i++;
    }
  }  //如果操作符棧中還有操作符，就把它彈出到字尾表達式隊列中
    while (!s.empty())
    {
      q.push(s.top());
      s.pop();
    }
}
double Cal()//計算字尾表達式
{
  double temp1, temp2;
  node cur, temp;
  while (!q.empty())//隻要字尾表達式隊列非空
  {
    cur = q.front();//cur記錄隊首元素
    q.pop();
    if (cur.flag == true)s.push(cur);//如果是操作數，直接壓入棧
    else//如果是操作符
    {
      temp2 = s.top().num;//彈出第二操作數
      s.pop();
      temp1 = s.top().num;//彈出第一操作數
      s.pop();
      temp.flag = true;//臨時記錄操作數
      if (cur.op == '+')temp.num = temp1 + temp2;//加法
      else if (cur.op == '-')temp.num = temp1 - temp2;//減法
      else if (cur.op == '*')temp.num = temp1*temp2;//乘法
      else temp.num = temp1 / temp2;//除法
      s.push(temp);//把該操作數壓入棧
    }
  }
  return s.top().num;//棧頂元素就是字尾表達式的值
}
int main()
{
  op['+'] = op['-'] = 1;//設定操作符的優先級、
  op['*'] = op['/'] = 2;
  while (getline(cin, str), str != "0")
  {
    for (string::iterator it = str.begin(); it != str.end(); it++)
    {
      if (*it == ' ')
      str.erase(it);//把表達式中的空格全部去掉
    }
    while (!s.empty())s.pop();//初始化棧
    change();//将中綴表達式轉換為字尾表達式
    printf("%.2f\n", Cal());//計算字尾表達式
  }
  return 0;
}