基本的思路是将中缀表达式转换为后缀表达式，消除括号，然后计算。后缀表达式又称逆波兰表达式。主要通过栈来实现。


中缀表达式转换为后缀表达式：
1.从左到右逐个扫描中缀表达式中的各项，遇到结束符“#” 转6，否则继续。这里选择想中追表达式中添加一个#或自行判断是否到字符串的末尾。
2.遇到操作数直接输出。
3.若遇到右括号 ，则连续出栈输出，直到遇到左括号为止。左括号出栈但不输出，遇到右括号也不输出。
4.若是其他操作符，则和栈顶操作符比较优先级，若小于等于栈顶操作符优先级，则连续出栈输出，直到大于栈顶操作符的优先级结束，操作符进栈。
5。
6.输出栈中剩余操作符，“#”除外。
这里我们将输入的一个表达式字符串转换为后缀，且输入表达式是正确无误的。
#include "Calculator.h"

int calculator::getPriorityInStack(char oper){
	if(oper == '#')return 0;
	else if(oper == '(')return 1;
	else if(oper == '*' || oper == '/')return 5;
	else if(oper == '+' || oper == '-')return 3;
	else if(oper == ')')return 7;
	return -1;
}
int calculator::getPriorityOutStack(char oper){
	if(oper == '#')return 0;
	else if(oper == '(')return 7;
	else if(oper == '*' || oper == '/')return 4;
	else if(oper == '+' || oper == '-')return 2;
	else if(oper == ')')return 1;
	return -1;
}
string calculator::changeToSuffix(string Prefix){
	int isp,icp,i = -1 ;
	string output = "";;
	operstack.push('#');
	while(++i < Prefix.length()){
		isp = getPriorityOutStack( Prefix[i]) ;
		if(isp == -1){
			output+=Prefix[i];
			output+=',';
		}
		else{
			icp = getPriorityInStack( operstack.top() );
			while(isp <= icp){
				output += operstack.top();
				operstack.pop();
				icp = getPriorityInStack( operstack.top() );
				output+=',';
			}
			operstack.push(Prefix[i]);
		}
		
	}
	while (!operstack.empty())
	{
		output+= operstack.top();
		operstack.pop();
		output+=',';
	}
	return output.substr(0,output.length()-3);
}


使用 逗号，将数字分开。
c++中没有split函数，之后对改好的后缀表达式的运算就只能一个个遍历了。


后缀表达式的计算：
扫描表达式，遇到操作数进栈，遇到操作符，出栈两个操作数，然后使用操作符进行计算，先出栈的放在操作符的右边，获得结果进栈，知道遇到结束符。
int calculator::getResultBySuffix(string Suffix){
	int i = 0;
	string buff;
	int a,b;
	while( i < Suffix.length()){
		if(Suffix[i] == ',')
			i++;
		buff = "";		
		while(Suffix[i] >='0' && Suffix[i]<='9'&& i <Suffix.length())
			buff += Suffix[i++];
		if(buff != ""){
			numstack.push(atoi(buff.c_str()));
		}else{
			a = numstack.top();
			numstack.pop();
			b =  numstack.top();
			 numstack.pop();
			if(Suffix[i] == '+')
				numstack.push(b+a);
			else if(Suffix[i] == '-')
				numstack.push(b-a);
			else if(Suffix[i] == '*')
				numstack.push(b*a);
			else if(Suffix[i] == '/')
				numstack.push(b/a);
			i++;
		}
	

	}
	i = numstack.top();
	numstack.pop();
	return i;
}

int calculator::getResult(string Prefix){
	return getResultBySuffix(changeToSuffix(Prefix));
}



完成计算。

原创作者：Daniel
时间：2017.10.29
地点：大连理工大学软件学院
表达式计算至少需要两个栈：1、数据栈 2、运算符栈
中缀表达式定义：
<表达式>::=<项> + <项> |<项> - <项> | <项>
项 ::= <因子> * <因子> | <因子> / <因子> | <因子>
<因子> ::= <常数> | (表达式)
<常数> ::= <数字> | <数字> <数字>
<数字> ::= 0|1|2|3|4|5|6|7|8|9
中缀表达式计算通常按照我们习惯的先乘除后加减，有括号先算括号。
逆波兰表达式定义：

<表达式>::=<项><项> + |<项>  <项> - | <项>
项 ::= <因子> <因子> *| <因子>  <因子>／ | <因子>
<因子> ::= <常数>
<常数> ::= <数字> | <数字> <数字>
<数字> ::= 0|1|2|3|4|5|6|7|8|9
在逆波兰表达式中，数字按照原来的顺序出现，运算放在参与运算的两个项或者因子后边
比如：
23 + （34 * 45）／（5 + 6 + 7）
23 34 45*  5 6 +7+／+
计算逆波兰表达式比中缀表达式要容易一些，具体过程如下：
1、扫描表达式，操作数入栈
2、遇到运算符，就在栈顶取出两个元素，用后取出的 操作 先取出的
3、将运算所得的数字进栈
4、循环123，直到表达式扫描完成，栈顶元素就是表达式的值
在计算中缀表达式时有两种方法：1、转化为后缀表达式 2、直接计算
1、中缀转化后缀方法：
1）定义操作数的栈内外优先级
2）扫描中缀表达式，遇到数字就输出
2）遇到运算符，就将预算符的优先级（栈外优先级）与栈顶元素比较
若栈外 高于 栈内 进栈
栈外 低于 栈内，依次弹出运算符输出，直到栈顶元素优先级小于或者等于栈外元素优先级
如果栈内外优先级相等，则栈顶元素弹出，不输出
2、直接计算和1 过程基本一致，需要在运算符出栈过程进行算术运算，同时需要管理两个栈。
#include<stdio.h>
#include<stdlib.h>
#include<stack>

int priorityisp(char op) {

    switch (op) {
        case '#':
            return 0;
            break;
        case '(':
            return 1;
            break;
        case '^':
            return 7;
            break;
        case '*':
        case '/':
            return 5;
            break;
        case '+':
        case '-':
            return 3;
            break;
        case ')':
            return 8;
            break;
        default:

            printf("error!");
            break;
    }

    return -1;
}

int priorityicp(char op) {

    switch (op)
    {
        case '#':
            return 0;
            break;
        case '(':
            return 8;
            break;
        case '^':
            return 6;
            break;
        case '*':
        case '/':
            return 4;
            break;
        case '+':
        case '-':
            return 2;
            break;
        case ')':
            return 1;
            break;
        default:
            printf("error!");
            break;
    }

    return -1;
}

char* changeExp(char* exp) {

    char* postfixExp = (char*)malloc(sizeof(char) * 20);
    std::stack<char> oper;
    oper.push('#');
    int i = 0;
    int j = -1;
    while (exp[i]) {

        switch (exp[i]) {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                postfixExp[++j] = exp[i];
                break;
            default:
                while (priorityicp(exp[i]) < priorityisp(oper.top())) {
                    postfixExp[++j] = oper.top();
                    oper.pop();
                }

                if (priorityicp(exp[i]) > priorityisp(oper.top()))
                    oper.push(exp[i]);

                else  {
                    oper.pop();
                }

                break;
        }
        i++;
    }

    postfixExp[++j] = '\0';
    return postfixExp;
}

int calculate(char* postfixExp) {

    std::stack<char> cal;
    int i = 0;

    while (postfixExp[i]) {

        switch (postfixExp[i]) {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                cal.push(postfixExp[i]);
                break;
            default:
                int num1 = cal.top() - '0';
                cal.pop();

                int num2 = cal.top() - '0';
                cal.pop();

                switch (postfixExp[i]) {

                    case '+':
                        cal.push(num2 + num1 + '0');
                        break;
                    case '-':
                        cal.push(num2 - num1 + '0');
                        break;
                    case '*':
                        cal.push(num2 * num1 + '0');
                        break;
                    case '/':
                        cal.push(num2 / num1 + '0');
                        break;
                }
        }
        i++;
    }

    return cal.top() - '0';
}

int main(int argc, char** argv) {

    char InfixExp[20];
    char* PostfixExp;
    int i = 0;

    while ((InfixExp[i] = getchar()) != '\n')
        i++;
    InfixExp[i] = '\0';
    PostfixExp = changeExp(InfixExp);
    printf("%d", calculate(PostfixExp));
    system("pause");

    return 0;
}

描述
后缀表达式这样一种类型的表达式，操作数在前，操作符在后。例如这样的一位数后缀表达式：
32+5*4-
对等的四则表达式为：(3+2)*5-4。
试编写程序，求解一个一位数的后缀表达式计算，表达式支持+,-,*,/操作，其中/为整除。
输入
表达式
输出
计算值
样例输入
32+5*4-
样例输出
21
提示
可使用栈
 
解题关键：
1. 理解后缀表达式如何计算
2. 当输入的是数字直接入栈
3. 当输入运算符时，直接出栈第一个和第二个运算数并且将计算结果入栈
4. 注意字符与数字之间的转换（因为输入的是字符串）
C++代码如下：
#include <iostream>
#include <stack>
using namespace std;
int computer(int a,char op,int b)//op代表运算符 a，b为操作数
{
	if(op == '+')
		return a+b;
	else if(op == '-')
		return a-b;
	else if(op == '*')
		return a*b;
	else
		return a/b;			
}
int main()
{
	stack<char> s1;
	string s;
	cin >> s;
	for(int i = 0; i < s.length(); i++)
	{
		if(s[i] == '+' || s[i] == '-' || s[i] =='*' || s[i] == '/')
		{//遇到运算符就要对栈顶两个元素进行计算
					
			int a = s1.top()-'0'; s1.pop();
			int b = s1.top()-'0'; s1.pop();//-’0’是为了将字符转换成数字
			int c = computer(b,s[i],a);
			s1.push(c+'0');
		}
		else
		{
			s1.push(s[i]);
		}	
	}
	cout<<s1.top()-'0';
	return 0;
}

最近在学习二叉树，学习了怎样计算算术表达式

计算算术表达式的大体思路是： 

1.   首先是将中缀表达式转换成后缀表达式 

2.  将后缀表达式，借助栈就能轻易的求出值 

例如： 

    （1+2）x3的后缀表达式是 12+3x，借助一个栈，将1,2放进去，在发现是+，将1,2弹出，计算1+2，计算出结果(3)，放进去，栈中有3,3再遇见‘x’号，将3,3弹出，计算出结果(9),最终计算出结果。

    //确定运算符的优先级
    HashMap<Character,Integer> map=new HashMap<Character,Integer>();
    public void initiall(){
        map.put('#', -1);
        map.put('+', 0);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 3);
    }
    //设置一个Linkedlist存放后缀表达式
    //设置一个Stack存放运算符
    private LinkedList<String> linkedlist=new LinkedList<String>();
    private Stack<Character> stack=new Stack<Character>();

接下来将算术表达式转换成后缀表达式



    public void opeator() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] char_str=br.readLine().toCharArray();
        stack.push('#');
        int i=0;
        while(i<char_str.length){
            if(char_str[i]=='('){
                stack.push(char_str[i]);
            }
            else if(char_str[i]==')'){
                Character temp=stack.pop();
                while(temp!='('){
                    linkedlist.add(temp.toString());
                    temp=stack.pop();
                }
            }
            else if(map.containsKey(char_str[i])){
                Character temp=stack.peek();
                while(temp!='('&&map.get(temp)>map.get(char_str[i])){
                    temp=stack.pop();
                    linkedlist.add(temp.toString());
                    temp=stack.peek();
                }
                stack.push(char_str[i]);
            }
            else{
                linkedlist.add(String.valueOf(char_str[i]));
            }
            i++;
        }
    }

转换成后缀表达式后，再根据栈求出结果



    public int getResult(){
        Iterator<String> iterator=linkedlist.iterator();
        Stack<Integer> stackInt=new Stack<Integer>();
        while(iterator.hasNext()){
            String str=iterator.next();
            if(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){
                int a=stackInt.pop();
                int b=stackInt.pop();
                int result=0;
                if(str.equals("+")){
                    result=a+b;
                }
                else if(str.equals("-")){
                    result=b-a;
                }
                else if(str.equals("*")){
                    result=a*b;
                }
                else if(str.equals("/")){
                    result=a/b;
                }
                stackInt.push(result);
            }
            else{
                stackInt.push(Integer.parseInt(str));
            }
        }
        return stackInt.pop();
    }

可能没有考虑出错的情况，有点不好。