学步园

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;

// 操作符优先级
int getWeight(char ch)
{
    switch (ch) 
	{
		case '/':
		case '*': return 2; 
		case '+':
		case '-': return 1;
		default : return 0;
   }
}

// 前缀表达式转换成后缀表达式
void infix2postfix(char infix[], char postfix[], int size) 
{
	stack<char> s;
	int weight;
	int i = 0;
	int k = 0;
	char ch;
	 
	while (i < size) 
	{
		ch = infix[i];
		if (ch == '(')
		{
			// 第一个括号直接压人堆栈
			s.push(ch);
			i++;
			continue;
		}
		if (ch == ')') 
		{
			 // 如果看到右括号，弹出所有元素并添加到后缀表达中，直到遇到左括号
			while (!s.empty() && s.top() != '(') 
			{
				postfix[k++] = s.top();
				s.pop();

			}
			// 去除左边的括号
			if (!s.empty()) 
			{
				s.pop();
			}
			i++;
			continue;
		}

		weight = getWeight(ch);
		if (weight == 0) 
		{
			postfix[k++] = ch; // 操作符直接添加
		}
		else 
		{
			// 运算符
			if (s.empty()) 
			{
				// 空则直接添加
				s.push(ch);
			}
			else 
			{
				// 从栈中弹出所有运算符，并添加到后缀表达式中，直到
				// 遇见比当前优先级更低的预算符
				while (!s.empty() && s.top() != '(' &&
					weight <= getWeight(s.top())) 
				{
					postfix[k++] = s.top();
					s.pop();
				}
				// 将当前的运算符压栈
				s.push(ch);
			}
		}
		i++;
	}
	 // 弹出剩下的运算符并添加后缀表达式中
	while (!s.empty()) 
	{
		postfix[k++] = s.top();
		s.pop();
	}
	postfix[k] = '\0'; // 解释符
}

void getTwoOffStack(stack<int>& theStack, int& first, int& second)
{
	second = theStack.top();  
	theStack.pop();
	first = theStack.top();
	theStack.pop ();
}

int postfixCalculate(string& theExpress)
{
   
   stack<int> theStack;           
   
   int first, second;
   for (unsigned int n = 0; n < theExpress.size(); n++)
   {
        switch (theExpress[n])
		{
		    case '*':
			    getTwoOffStack(theStack, first, second);
			    theStack.push(first * second);
            break;
         
		    case '/':
			    getTwoOffStack(theStack, first, second);
				if (0 != second)
					theStack.push(first / second);
				else
					cout << "Div Zero!" << endl;
            break;
         
		    case '+':
			    getTwoOffStack (theStack, first, second);
			    theStack.push (first + second);
            break;
         
		    case '-':
			    getTwoOffStack(theStack, first, second);
			    theStack.push(second - first);
            break;

		    default:
			    char str[3];
      		    str [0] = theExpress[n];
      		    str [1] = '\0';
			    theStack.push(atoi(str)); // 数字转整形
			break;
       }
    }

    int returnVal = theStack.top();
    theStack.pop();
   
    return returnVal;
}



// main
int main() 
{
	char infix[] = "1+2*4*8-10";
    int size = strlen(infix);
    char postfix[100];
    infix2postfix(infix,postfix,size);

	cout<<"\nInfix Expression :: "<<infix;
	cout<<"\nPostfix Expression :: "<<postfix;
	int resVal = postfixCalculate(string(postfix));
	cout << endl << resVal << endl;
	return 0;
}