题解 P1175 【表达式的转换】

__charlie520__ · 2020-03-16 16:04:20 · 题解

本题基本可以分为3步：

• 读入中缀表达式
• 中缀表达式转换为后缀表达式并输出
• 计算后缀表达式并输出过程

首先我们来看看如何读入中缀表达式。

一般输入字符有三种方法：

1. for + scanf

举个例子：

for(int i = 0;i < n;i++)
    scanf("%c",x);

显然此题我们不知道n是多少，所以pass。

2. while(cin)

举个例子：

while(cin >> x) {
    //做一些事情
}

然而这样太麻烦了，而且只是读入而已，不需要边输入边做事，果断pass。

3.

聪慧的我发现了表达式之间没有空格。

(大佬早就看见了)

于是，第三种方法脱险而出：string!

string s1;
cin >> s1;

直接输入字符串即可。

然后我们看看如何将中缀转后缀。

主要使用的数据结构：栈
首先创建一个函数来回复优先级，一共3种情况

• +,-优先级最低，用1表示
• 其次是×,/，用2表示
• ^优先级最高，用3表示

代码：

int p(char ch) {
    if(ch == '+' || ch == '-') return 1;
    if(ch == '*' || ch == '/') return 2;
    if(ch == '^') return 3;
    else return 0;//此处可不写，防止报错
}

表达式的符号共有4种类型：

• 数字
  直接放入后缀表达式
• 左括号
  直接压入栈
• 右括号
  while(栈顶不为左括号) {
  栈顶元素放入后缀表达式；
  弹出栈顶元素；
  } 弹出栈顶元素；
• 为普通运算符（+,-,*,/,^）
  while(栈不空&&栈顶运算符优先级比该运算符优先级高） {
  栈顶元素放入后缀表达式；
  弹出栈顶元素；
  }
  将该运算符压入栈；

最后将栈内剩下的所有元素放入后缀表达式并弹出
代码：

for(int i = 0;i < len;i++) {
    if(s1[i] >= '0' && s1[i] <= '9')//数字
        s2 += s1[i];
    else if(s1[i] == '(')//左括号
        st.push('(');
    else if(s1[i] == ')') {//右括号
        while(st.top() != '(') {
            s2 += st.top();
            st.pop();
        }
        st.pop();
    }
    else {//普通运算符
    while(!st.empty() && p(st.top()) >= p(s1[i])) {
            s2 += st.top();
            st.pop();
        }
        st.push(s1[i]);
    }
}
while(!st.empty()) {//全部弹出
    s2 += st.top();
    st.pop();
}

切记！输出后缀表达式！用空格隔开！

int la = s2.length();
    for(int i = 0;i < la;i++)
        cout << s2[i] << " ";
    cout << endl;//末尾一定有换行！

使用la存长度，否则会非常慢！

接下来是重头戏：计算后缀表达式并输出运算过程

计算后缀表达式也使用：栈
一共有两种情况：

• 数字
  直接压入栈。（注意要转为int类型哦！）
• 运算符
  取出栈顶两元素进行计算，并压入栈中
  首先我们建立一个函数来进行两数的计算
  为+ , - , × , /
  return a （+ , - , × , /） b；
  否则为^,使用(int)pow(a, b);进行计算，需要改int。
  代码：

  int numans(int a,char c,int b) {
  if(c == '+') return a + b;
  if(c == '-') return a - b;
  if(c == '*') return a * b;
  if(c == '/') return a / b;
  if(c == '^') return (int)pow(a, b);
  } 

  然后将运算过程输出出来。

• 输出所有栈内元素
• 输出还未计算的后缀表达式

代码：

for(int i = 0;i < la;i++) {
        if(s2[i] >= '0' && s2[i] <= '9') { 
            st2.push_back(s2[i] - '0');
        }
        else {
            int a, b;
            a = st2.back();
            st2.pop_back();
            b = st2.back();
            st2.pop_back();
            st2.push_back(numans(b,s2[i],a));
            for (list<int>::iterator it = st2.begin(); it != st2.end(); ++it)
                cout << *it << " ";

            for (int j = i + 1; j < la; j ++)
                cout << s2[j] << " ";
            cout << endl;
        } 
    } 

然后是最难的：

return 0;
}

这样，你就可以AC这道题了！

AC CODE

请勿复制黏贴，可以借鉴学习。

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
stack<char> st;
list<int> st2;
int p(char ch) {
    if(ch == '+' || ch == '-') return 1;
    if(ch == '*' || ch == '/') return 2;
    if(ch == '^') return 3;
    else return 0;
}
int numans(int a,char c,int b) {
    if(c == '+') return a + b;
    if(c == '-') return a - b;
    if(c == '*') return a * b;
    if(c == '/') return a / b;
    if(c == '^') return (int)pow(a, b);
} 
int main() {
    cin >> s1;
    int len = s1.length();
    for(int i = 0;i < len;i++) {
        if(s1[i] >= '0' && s1[i] <= '9')
            s2 += s1[i];
        else if(s1[i] == '(')
            st.push('(');
        else if(s1[i] == ')') {
            while(st.top() != '(') {
                s2 += st.top();
                st.pop();
            }
            st.pop();
        }
        else {
            while(!st.empty() && p(st.top()) >= p(s1[i])) {
                s2 += st.top();
                st.pop();
            }
            st.push(s1[i]);
        }
    }
    while(!st.empty()) {
        s2 += st.top();
        st.pop();
    }
    int la = s2.length();
    for(int i = 0;i < la;i++)
        cout << s2[i] << " ";
    cout << endl;

    for(int i = 0;i < la;i++) {
        if(s2[i] >= '0' && s2[i] <= '9') { 
            st2.push_back(s2[i] - '0');
        }
        else {
            int a, b;
            a = st2.back();
            st2.pop_back();
            b = st2.back();
            st2.pop_back();
            st2.push_back(numans(b,s2[i],a));
            for (list<int>::iterator it = st2.begin(); it != st2.end(); ++it)
                cout << *it << " ";

            for (int j = i + 1; j < la; j ++)
                cout << s2[j] << " ";
            cout << endl;
        } 
    } 
    return 0;
}