苏州OJ c003: 中缀转后缀

朱雀 2022-08-14 04:55 156阅读 0赞

**内容：**

【问题描述】  
请编写程序将一个中缀表达式转换为后缀表达式。  
【输入】  
仅一行，是一个中缀表达式。输入的符号中只有这些基本符号“0123456789+-\*/()”，并且不会出现形如2\*-3的格式，所有数字都是个位数，“/”表示整除运算。  
【输出】  
仅一行，是转换后的后缀表达式。数字之间、运算符之间、数字和运算符之间都用一个空格隔开（参见样例）。  
【样例】  
ex3.in  
8-(3+2\*6)/5+4  
ex3.out

8 3 2 6 \* + 5 / - 4 +

这道题对于很多数据结构书中的栈一章一般都会提到，思路清晰的话很快就能做出来，没什么陷阱。

/*
     * 输入一串中缀表达式，对每一个字符进行提取
     * 1.如果是数字，直接放到rs中
     * 2.如果是符号，与栈顶元素进行比较
     *		⑴如果栈为空，直接放进栈中
     *		⑵如果栈不为空，则一直pop到rs中
     *		  直到①栈为空②碰到优先级比新符号低的元素为止
     *		  再把新符号压入栈中
     * 需要注意的到最后栈可能还没空，所以要一个个pop到rs中 
     *
     * 我的两个辅助函数isOper用来判断是否为符号
     *					level用来判断优先级
     */
    #include <iostream>
    #include <string>
    #include <stack>
    #define OUTSTACK 1
    #define INSTACK 2
    #define EQUAL 0
    using namespace std;
    
    bool isOper(char c);
    int level(char lhs, char newOper);
    
    int main()
    {
    	string s, rs;			// rs是结果
    	stack<char> operStk;	// 符号栈
    
    	cin >> s;
    
    	string::iterator iter = s.begin();
    	while (iter != s.end()) {
    		// 为符号
    		if (isOper(*iter)) {
    			// 栈不为空
    			if (!operStk.empty()) {
    				int lv = level(operStk.top(), *iter);
    				switch (lv)
    				{
    				case INSTACK:
    					operStk.push(*iter);
    					++iter;
    					break;
    				case OUTSTACK:
    					rs += operStk.top();
    					operStk.pop();
    					break;
    				case EQUAL:
    					operStk.pop();
    					++iter;
    					break;
    				}
    			}
    			else
    				operStk.push(*iter++);
    		}
    		// 为数字
    		else {
    			rs += *iter++;
    		}
    	}
    	// 清空栈
    	while (!operStk.empty()) {
    		rs += operStk.top();
    		operStk.pop();
    	}
    	// 输出
    	iter = rs.begin();
    	while (iter != rs.end()) {
    		cout << *iter;
    		if (++iter != rs.end()) {
    			cout << " ";
    		}
    	}
    
    	return 0;
    }
    
    bool isOper(char c) {
    	return (c == '+') || (c == '-') || (c == '*')
    		|| (c == '/') || (c == '(') || (c == ')');
    }
    
    int level(char lhs, char newOper) {
    	switch (newOper)
    	{
    	case '+':
    	case '-':
    		if (lhs == '(') return INSTACK;
    		else return OUTSTACK;
    	case '*':
    	case '/':
    		if (lhs == '+' || lhs == '-')
    			return INSTACK;
    		else if (lhs == '(')
    			return INSTACK;
    		else
    			return OUTSTACK;
    	case '(':
    		return INSTACK;
    	case ')':
    		if (lhs == '(')
    			return EQUAL;
    		else
    			return OUTSTACK;
    	}
    }