C++中綴表達式轉字尾表達式

最近在看電腦相關的東西，然後想自己實作一下簡單的中綴表達式轉字尾表達式。
           

環境Visual Studio 2017->c++控制台項目

本文僅實作中綴表達式轉字尾表達式，（中綴轉字尾以及）字尾表達式計算，請點選下面的連結：

字尾表達式計算

1. 棧内外元素優先級

isp棧内元素優先級(in stack priority)

icp棧外元素優先級(in coming priority)

2.算法思想

(1)初始化棧，将結束符‘#’入棧，在輸入字元串末尾添加’#’。

(2)若是數字，将擷取整個數字串，然後直接輸出到隊列(string)q中

否則将棧頂元素s.top()與棧外元素(string)intput[i]的優先級做比較

·1·若isp(s.top()) > icp(input[i]),棧内優先級高，則出棧，壓入輸出隊列q。

此時

需将棧内所有優先級比棧外元素優先級高的元素出棧，并壓入輸出隊列q中，直到優先等級是<=。再重新執行<或=操作。

·2·若isp(s.top()) < icp(input[i]),棧外元素優先級高，則進棧

·3·若isp(s.top()) = icp(input[i]),棧内外優先級相等，則出棧。

(3)直至input中所有元素被讀取完，也就是棧内的#與input的#比對，此時隊列q中的元素輸出即為所求字尾表達式。

3.代碼實作

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

stack<char> s;//存放運算符的棧
queue<string> q;//輸出隊列（用于計算字尾表達式）
stack<double> sum;//用于計算字尾表達式（本文未實作計算字尾表達式）
string str = "";//讀取整個數字串并儲存

int isp(char c)//棧内元素優先級判斷
{
 switch (c)
 {
 case '#':
  return 0;
 case '(':
  return 1;
 case '+':
 case '-':
  return 3;
 case '*':
 case '/':
 case '%':
  return 5;
 case ')':
  return 6;
 }
}
int icp(char c)//棧外元素優先級判斷
{
 switch (c) {
 case '#':
  return 0;
 case ')':
  return 1;
 case '+':
 case '-':
  return 2;
 case '*':
 case '/':
 case '%':
  return 4;
 case '(':
  return 6;
 }
}
void postfix(string input)//中綴表達式轉字尾表達式代碼
{
	s.push('#');//将#壓入棧頂
 input += '#';//添加#号作為結束符
 for (int i = 0; i < input.length(); i++)
 {
  if ((input[i] >= '0' && input[i] <= '9') || input[i] == '.')
  {
   str += input[i];
  }
  else
  {
   if (str.length() > 0)//将數放入直接輸出到隊列中
   {
    q.push(str);
    str = "";
   }
   while (isp(s.top()) > icp(input[i]))
   {
    string a;//因為不能直接在棧和隊列間轉換字元和字元串類型，是以先将字元轉成 字元串再出棧進隊列
    a = s.top();
    q.push(a);
    s.pop();
   }
   //判斷站外元素優先級決定元素是應該去除（=），還是進棧(<)
   if (isp(s.top()) == icp(input[i]))
   {
    s.pop();
   }
   else
   {
    s.push(input[i]);
   }
  }
 }
}


int main()
{
 string input;
 string och;
 cin >> input;
 postfix(input);
 while (q.empty() == false)//隊列不為空則輸出隊列元素
 {
  och=q.front();
  cout << och ;
  q.pop();
 }
}
           

實驗結果

輸入:(5-8*(8-7))*9

輸出：結果沒問題，輸入的時候不要将括号打成中文。

本文參照

資料結構：用于面向對象方法與C++語言描述/殷人昆主編。 —2版(第99頁)

寄語

有什麼問題可以評論區交流，寫了也不一定回，回了也不一定對，對了也不一定能用，能用了也不一定能對。。。。。。。