中缀变为后缀

  1 /*
  2 * main.cpp
  3 *  Created on: 2017-06-06
  4 *      Author: yanhao
  5 */
  6 #include<iostream>
  7 #include<string.h>
  8 #include<stack>
  9 using namespace std;
 10 void Change(char inorder[], char post[], int& m)//将中缀表达式转换为后缀表达式，参数m跟踪后缀表达式长度
 11 {
 12     int n = strlen(inorder);//获取中缀表达式的长度
 13     stack<char> czf;//定义一个char型堆栈用于存放操作符;
 14     for (int i = 0; i<n; i++)
 15     {
 16         if (inorder[i] >= '0'&&inorder[i] <= '9')//若为操作数，直接添加到后缀表达式数组中
 17         {
 18             post[m] = inorder[i];
 19             m++;
 20         }
 21         if (inorder[i] == '(')czf.push(inorder[i]);//若为‘（’直接压入堆栈
 22         if (inorder[i] == '+')//若为‘+’与栈顶比较优先级，较低则将栈顶操作符加到数组中，在将‘+’压栈
 23         {
 24             if (!czf.empty() && (czf.top() == '*' || czf.top() == '/' || czf.top() == '-'))
 25             {
 26                 post[m++] = czf.top(); czf.pop(); czf.push(inorder[i]);
 27             }
 28             else{ czf.push(inorder[i]); }
 29         }
 30         if (inorder[i] == '-')//若为‘-’与栈顶比较优先级，较低则将栈顶操作符加到数组中，将‘-’压栈
 31         {
 32             if (!czf.empty() && (czf.top() == '*' || czf.top() == '/'))
 33             {
 34                 post[m++] = czf.top(); czf.pop(); czf.push(inorder[i]);
 35             }
 36             else{ czf.push(inorder[i]); }
 37         }
 38         if (inorder[i] == '*' || inorder[i] == '/')czf.push(inorder[i]);//若为‘*’或‘/’直接压栈
 39         if (inorder[i] == ')')//若遇到‘）’将栈中的操作符依次弹出直到遇到‘（’结束
 40         {
 41             while (czf.top() != '(')
 42             {
 43                 post[m++] = czf.top(); czf.pop();
 44             }
 45             czf.pop();//弹出‘（’
 46         }
 47     }
 48     while (!czf.empty())//将栈中剩余元素依次弹出到后缀表达式数组中
 49     {
 50         post[m++] = czf.top(); czf.pop();
 51     }
 52 }
 53 int Calculate(char post[], int n)//通过后缀表达式求值
 54 {
 55     stack<int>ss;//定义int型堆栈存放操作数及每次运算结果
 56     int a, b, c, result;
 57     for (int i = 0; i<n; i++)
 58     {
 59         if (post[i] >= '0'&&post[i] <= '9')
 60         {
 61             ss.push((post[i] - '0'));//将char型转为int型
 62         }
 63 
 64         if (post[i] == '-')
 65         {
 66             b = ss.top(); ss.pop(); a = ss.top(); ss.pop();
 67             c = a - b; ss.push(c);
 68         }
 69         if (post[i] == '+')
 70         {
 71             b = ss.top(); ss.pop(); a = ss.top(); ss.pop();
 72             c = a + b; ss.push(c);
 73         }
 74         if (post[i] == '*')
 75         {
 76             b = ss.top(); ss.pop(); a = ss.top(); ss.pop();
 77             c = a*b; ss.push(c);
 78         }
 79         if (post[i] == '/')
 80         {
 81             b = ss.top(); ss.pop(); a = ss.top(); ss.pop();
 82             c = a / b; ss.push(c);
 83         }
 84     }
 85     result = ss.top();//得到最后栈顶元素
 86     ss.pop();//清空栈
 87     return result;
 88 }
 89 int main()
 90 {
 91 
 92     char in[100]; char a; int i = 0;
 93     cout << "请输入中缀表达式（#表示结束）：";
 94     while (cin >> a)//循环获取输入直到遇到‘#’结束
 95     {
 96         if (a == '#')break;
 97         in[i++] = a;
 98     }
 99     char po[100]; int n = 0;
100     Change(in, po, n);
101     cout << "后缀表达式为:";
102     for (int j = 0; j<n; j++)cout << po[j] << "";
103     cout << endl;
104     cout << "运算结果为:" << Calculate(po, n) << endl;
105     system("pause");
106     return 0;
107 }